Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

G. Cereal Bushes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas is a very peculiar cereal farmer. He plants bushes of fruit-flavored cereal instead of trees like everyone else.

Thomas' farm is a rectangular grid size $$$n \times m$$$ ($$$1 \leq n,m \leq 64$$$). The rows are numbered $$$1\dots n$$$ from top to bottom and the columns are numbered $$$1 \dots m$$$ from left to right. Cell ($$$x$$$, $$$y$$$) is in row $$$x$$$ and column $$$y$$$. Some cells will be empty, and others he will plant a bush in, but he hasn't planted any yet.

Every morning Thomas will take a walk starting from cell ($$$1$$$, $$$1$$$) to cell ($$$n$$$, $$$m$$$). If he is currently in cell ($$$x$$$, $$$y$$$), he can only move to cell ($$$x + 1$$$, $$$y$$$) or cell ($$$x$$$, $$$y + 1$$$), and he must stay within the grid at all times. He can't move into cells that have a bush. It is possible that there is no valid path, or that he is unable to enter cell ($$$1$$$, $$$1$$$) due to there being a bush (in such a case there would also be no valid paths).

Please help Thomas first pick the dimensions of his grid, and then a way to plant bushes such that there are exactly $$$k$$$ different paths that Thomas can take on his morning walk. Two paths are considered different if there is a cell visited in one path but not the other. It can be shown that under the constraints of the problem this is always possible.

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases. Each test case will be one line that has an integer, $$$k$$$ ($$$0 \leq k \leq 10^{18}$$$).

Output

Print the answer for each of the $$$t$$$ test cases.

In the first line, print two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 64$$$).

In the following line, print $$$x$$$, the number of bushes Thomas needs to plant. $$$x$$$ lines should come after, each containing two integers $$$r$$$ and $$$c$$$ , meaning Thomas should plant a bush in cell ($$$r$$$, $$$c$$$) ($$$1 \leq r \leq n, 1 \leq c \leq m$$$).

All the bushes should be distinct. If there are multiple valid solutions, print any.

Example
Input
2
1
5
Output
1 1
0
3 3
1
1 3
Note

In the first test case a $$$1 \times 1$$$ grid with no bushes has only one path in it satisfying the conditions.

For the second test case, without any bushes there are $$$5$$$ valid paths, but the bush in cell ($$$1$$$, $$$3$$$) blocks one of them, so there are only $$$4$$$ paths.

Problem Credits: Thomas Meeks