原题：Pascal Walk（含图，需科学上网）

Problem
Pascal’s triangle consists of an infinite number of rows of an increasing number of integers each, arranged in a triangular shape.

Let us define (r, k) as the k-th position from the left in the r-th row, with both r and k counted starting from 1. Then Pascal’s triangle is defined by the following rules:

The r-th row contains r positions (r, 1), (r, 2), …, (r, r).
The numbers at positions (r, 1) and (r, r) are 1, for all r.
The number at position (r, k) is the sum of the numbers at positions (r - 1, k - 1) and (r - 1, k), for all k with 2 ≤ k ≤ r - 1.

In this problem, a Pascal walk is a sequence of s positions (r1, k1), (r2, k2), …, (rs, ks) in Pascal’s triangle that satisfy the following criteria:

r1 = 1 and k1 = 1.
Each subsequent position must be within the triangle and adjacent (in one of the six possible directions) to the previous position. That is, for all i ≥ 1, (ri + 1, ki + 1) must be one of the following that is within the triangle: (ri - 1, ki - 1), (ri - 1, ki), (ri, ki - 1), (ri, ki + 1), (ri + 1, ki), (ri + 1, ki + 1).
No position may be repeated within the sequence. That is, for every i ≠ j, either ri ≠ rj or ki ≠ kj, or both.
Find any Pascal walk of S ≤ 500 positions such that the sum of the numbers in all of the positions it visits is equal to N. It is guaranteed that at least one such walk exists for every N.

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line containing a single integer N.

Output
For each test case, first output a line containing Case #x:, where x is the test case number (starting from 1). Then, output your proposed Pascal walk of length S ≤ 500 using S additional lines. The i-th of these lines must be ri ki where (ri, ki) is the i-th position in the walk. For example, the first line should be 1 1 since the first position for all valid walks is (1, 1). The sum of the numbers at the S positions of your proposed Pascal walk must be exactly N.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.

Test set 1 (Visible Verdict)
1 ≤ N ≤ 501.

Test set 2 (Visible Verdict)
1 ≤ N ≤ 1000.

Test set 3 (Hidden Verdict)
1 ≤ N ≤ 10^9.

Sample

Input

3
1
4
19

Output

Case #1:
1 1
Case #2:
1 1
2 1
2 2
3 3
Case #3:
1 1
2 2
3 2
4 3
5 3
5 2
4 1
3 1

/**
此处tourist用了2的倍数来凑成n（类似二进制表示）
pascal三角形每一行的和是前一行的两倍
**/
/**
 *    author:  tourist
 *    created: 11.04.2020 04:17:10       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int qq = 1; qq <= tt; qq++) {
    cout << "Case #" << qq << ":\n";
    int n;
    cin >> n;
    int rows = min(30, n);//最多使用30行
    n -= rows;//减去每一行最左边的1，用来在每行之间行走
    vector<int> a(rows);//看看每一行是否需要被加上
    for (int row = rows - 1; row >= 0; row--) {
    //从最后一行开始走，若n比该行大，则加上这行所有的和
      if (n >= (1 << row) - 1) {
        a[row] = 1;
        n -= (1 << row) - 1;
      }
    }
    rows += n;//余下的n用来增加行数上的1来凑（即往下走边边）
    a.resize(rows);
    int side = 0;
    for (int row = 0; row < rows; row++) {
      if (a[row] == 1) {//需要加的这一行，
      //若位于左边，则从左往右走，否则从右往左走
        if (side == 0) {
          for (int j = 0; j <= row; j++) {
            cout << row + 1 << " " << j + 1 << '\n';
          }
        } else {
          for (int j = row; j >= 0; j--) {
            cout << row + 1 << " " << j + 1 << '\n';
          }
        }
        side ^= 1;
      } else {//若这行不需要加，则走边边然后跳过
        if (side == 0) {
          cout << row + 1 << " " << 1 << '\n';
        } else {
          cout << row + 1 << " " << row + 1 << '\n';
        }
      }
    }
  }
  return 0;
}