406736: GYM102512 E Valentine

It's Valentine's Day and Takitsubo wants to make a chocolate bar for Hamazura! The chocolate bar can be pictured as a rectangular grid, where each cell has an integer value of sweetness.

Hamazura likes to cut out a $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle from the chocolate bar and eat it first (here $$$K$$$ is any positive integer). A $$$1 \times K$$$ (or $$$K \times 1$$$) subrectangle of the chocolate bar is delicious if the sweetness level of the cells are strictly monotonic, i.e. strictly decreasing or increasing from left to right (or top to bottom).

Takitsubo knows that Hamazura's favourite number is $$$X$$$, so she wants to create the chocolate bar so that there are exactly $$$X$$$ ways to cut out a delicious $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle. Can you help her create such a chocolate?

There will be multiple testcases per test file.

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 50$$$), denoting the number of testcases.

The next $$$T$$$ lines of input contain a single integer $$$X$$$ ($$$1 \le X \le 7995051$$$), denoting Hamazura's favourite number.

For each test case, output two space-separated integers, $$$N, M$$$ ($$$1 \le N, M \le 200$$$) on the first line, denoting the dimensions of the chocolate bar.

The next $$$N$$$ lines should contain $$$M$$$ space-separated integers each, where the numbers in the $$$i$$$-th line denote the sweetness level of the cells in the $$$i$$$-th row. All sweetness levels must be a nonnegative integer not exceeding $$$10^{6}$$$.

Subtask 1 (3 points): $$$X \le 200$$$

Subtask 2 (14 points): $$$X \le 40000$$$

Subtask 3 (20 points): $$$2222222 \le X \le 3333333$$$

Subtask 4 (20 points): $$$X \le 4567890$$$

Subtask 5 (20 points): $$$X \le 6666666$$$

Subtask 6 (11 points): $$$X \le 7777777$$$

Subtask 7 (12 points): No additional constraints

7
3
14
1
4
9
7
113

1 2
2 14
2 3
9 4 1
2 0 2
1 1
1
3 1
3
1
1
1 5
2 1 0 1 1
2 2
14 2
20 20
6 6
0 1 2 3 4 6
7 1 2 3 8 5
3 6 0 1 4 4
2 5 0 4 4 1
9 7 5 1 0 3
0 6 2 4 4 9

Let's look at the second testcase, $$$X = 14$$$.

There are $$$6$$$ ways to cut out a $$$1 \times 1$$$ delicious subrectangle, namely each of the $$$6$$$ cells of the chocolate bar.

There are $$$3$$$ ways to cut out a $$$2 \times 1$$$ delicious subrectangle, namely each of the $$$3$$$ columns of the chocolate bar.

There are $$$4$$$ ways to cut out a $$$1 \times 2$$$ delicious subrectangle, as all possible $$$1 \times 2$$$ subrectangles you can cut out are delicious.

There is one way to cut out a $$$1 \times 3$$$ delicious subrectangle, namely the top row of the chocolate bar.

Note that the $$$1 \times 3$$$ subrectangle corresponding to the bottow row of the chocolate bar is not delicious, because it is neither strictly increasing from left to right or right to left.

Hence, there are a total of $$$6 + 3 + 4 + 1 = 14$$$ ways to cut out a delicious $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle, as desired.

You can verify the other sample cases by hand.