Description

Jernej feels very bored at night, so he invents a game. He wants to use number cards to build a tower. At the beginning, he writes the number $1$ on a card.

Jernej may write a new number on another card and place it on the top of the tower. This new number must be equal to the sum of the numbers in some consecutive segment of the current tower. In other words, suppose there are already $n$ numbers in the tower. You may choose any segment $[l,u]$ in the tower, compute the sum of this segment, and add the resulting new number to the top of the tower, where $1\le l\le u\le n$.

Jernej wants to build $T$ towers (equivalently, multiple queries). The top number of each tower is one of $T$ (possibly different) target numbers he wants. You need to help him find the minimum number of steps to build these towers and output a corresponding plan.

Input Format

The first line contains an integer $T$, the number of towers.

The next $T$ lines each contain an integer $q$, meaning Jernej wants to build a tower whose top number is $q$.

It is guaranteed that a solution exists.

Output Format

For each query $q$:

• Output one line containing an integer $s$ ($0\le s\le 10^3$), the minimum number of steps.
• Then output $s$ lines, each containing two integers $l,u$ separated by a space, describing the plan to build the tower (print earlier operations first).

3
2
3
7

2
1 1
1 2
3
1 1
2 2
1 3
4
1 1
1 2
2 3
1 4​

Hint

Special Judge Scoring Rules

This problem has $10$ test points. For each test point, the scoring rules are:

• For any tower in the test point, if the minimum number of steps output by your program is exactly the same as the standard answer, then you will get $10$ points for this test point.
• For any tower in the test point, if your program’s output is incorrect, you get $0$ points (during judging, if the output is incomplete you may get UKE).
• If your answer is not optimal but still correct, then for the $i$-th tower in this test point, your score is $\text{score}_i =1+\dfrac{\text{minimum steps}}{\text{solution steps}}\times 7$, where $\text{minimum steps}$ is the minimum number of steps in the correct answer, and $\text{solution steps}$ is the answer output by your program. The final score of this test point is $\min\limits_{i\in [1,T]} \{\text{score}_i\}$. Round up to two decimal places.

Sample Input/Output Explanation

Query 1 Explanation:

• Jernej wants to build a tower with top number $2$. Initially the tower is $\{1\}$ (the left side is the bottom and the right side is the top).
• Step 1: choose segment $[1,1]$, sum all elements in $\{1\}$ to get $1$, now the tower is $\{1,1\}$.
• Step 2: choose segment $[1,2]$, sum all elements in $\{1,1\}$ to get $2$, now the tower is $\{1,1,2\}$. The requirement of the query is now satisfied.

Query 2 Explanation:

• There is more than one way to build a tower whose top is $3$. Besides the one in the sample output, the following is also a correct answer:

1 1
1 2
2 3

Constraints

This problem uses bundled testdata and has 7 subtasks.

• Subtask 1 (1 test case - 10 points): $T\le 10,q\le 10$.
• Subtask 2 (1 test case - 10 points): $T\le 20,q\le 20$.
• Subtask 3 (1 test case - 10 points): $T= 100,q\le 100$.
• Subtask 4 (1 test case - 10 points): $T= 10^3,q\le 10^4$.
• Subtask 5 (1 test case - 10 points): $T= 10^3,q\le 10^5$.
• Subtask 6 (1 test case - 10 points): $T= 10^3,q\le 10^6$.
• Subtask 7 (1 test case - 10 points): $T= 10^3,q\le 10^9$.
• Subtask 8 (1 test case - 10 points): $T= 10^3,q\le 10^{12}$.
• Subtask 9 (2 test cases - 20 points): no additional constraints.

For all testdata, it is guaranteed that $1\le T\le 10^3,1\le q\le 10^{18}$.

Notes

The original problem is from: eJOI2019 Problem D. Tower.

Translation provided by: @_Wallace_.

Translated by ChatGPT 5