Dynamite is an [effective tool](https://youtu.be/7AheBqBk0iQ?t=433) for clearing ice to allow logs to flow downstream in the great Canadian log drive. But as every Canadian knows, successful use of dynamite requires a certain finesse. Logan the logging director is planning to hook up a network of dynamite sticks using fuse wires so that they may be detonated from afar.

Logan would like to use at most 2000 sticks of dynamite and at most 2000 fuse wires to build his dynamite network at a certain job site. He'll number the sticks from \(1\) to \(N\), and the wires from \(1\) to \(M\) (for some \(N\) and \(M\) of his choice). Each fuse wire is used to connect two different sticks of dynamite together. No two fuse wires may be used to connect the same unordered pair of sticks. The resulting dynamite network must all be connected (that is, it must be possible to reach each dynamite stick from each other stick by following a sequence of connected wires and sticks).

There's just one problem: sticks of dynamite are not individually powerful enough to break the thick ice. Logan must rely on *chain explosions* to amplify the dynamite's power. A potential chain explosion can occur anywhere in Logan's network where there is an ordered triple \((a, b, c)\) of distinct sticks of dynamite such that sticks \(a\) and \(b\) are connected by a fuse wire, as are sticks \(b\) and \(c\). Logan would like to build a network with exactly \(K\) potential chain explosions, where \(K\) is an even integer. Any less than \(K\), and there might not be enough ice-breaking power; any more than \(K\), and he risks damaging the logs.

Help Logan bust some ice by constructing *any* valid dynamite network for the given value of \(K\). Please note that at least one valid network exists for each possible valid value of \(K\).

# Constraints

\(1 \le T \le 100\)
\(2 \le K \le 2,000,000\)
\(K\) is even

The sum of \(K\) across all job sites is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of job sites. For each job site, there is a line containing a single integer \(K\).

# Output

For the \(i\)th job site, print a line containing *"Case #i: "*, followed by 2 integers \(N\) and \(M\), the number of sticks of dynamite and fuse wires your network will use \((1 \le N, M \le 2000)\). After that, print \(M\) more lines, the \(j\)th of which contains 2 integers \(A_j\) and \(B_j\), the two sticks of dynamite connected by the \(j\)th fuse wire \((1 \le A_j, B_j \le N, A_j \ne B_j)\).

# Explanation of Sample

***Note: For each job site, other outputs would also be accepted.***

For the first job site, the chosen network (depicted below) has exactly 2 potential chain explosions (involving dynamic stick triples \((1, 2, 3)\) and \((3, 2, 1)\)), as required.

{{PHOTO_ID:636021084002078}}

For the second job site, the chosen network (depicted below) has exactly 6 potential chain explosions (involving sticks \((1, 2, 3)\), \((1, 3, 2)\), \((2, 1, 3)\), \((2, 3, 1)\), \((3, 1, 2)\), and \((3, 2, 1)\)).

{{PHOTO_ID:2943967372557617}}

The following output would *not* be accepted, due to having a fuse wire connecting a stick of dynamite to itself (stick 3) and having two fuse wires connecting the same unordered pair of dynamite sticks (sticks 1 and 2):

```
3 5
1 2
2 1
2 3
3 3
3 1
```

The following output would also *not* be accepted, due to the dynamite network not being connected:

```
7 5
1 2
2 3
3 4
5 6
6 7
```

For the third job site, the chosen network is as follows:

{{PHOTO_ID:326196371830360}}