시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Farmhand Jernej gets bored in the evenings, thus he invented a simple game. He wants to build a tower from numbers on pieces of paper. He starts with a piece of paper and writes 1 on it.

Jernej can write another number on a piece of paper and place it on top of the tower. The new value on the top of the tower must be a valid sum of numbers on consecutive papers comprising the tower. Let's say there are currently n pieces of paper comprising the tower. He makes a sum of numbers in the tower within arbitrary positions [l, u], where 1 ≤ lun and puts the sum on top.

Jernej wants to produce T towers with desired numbers on top. Help him find out the required steps. He also asks you to minimize the number of those steps.

입력

In the first line of input, you will be given a positive integer T (number of different towers Jernej wants to produce).

In each of the next T lines, there will be one positive integer q , the value Jernej wants to produce at the end. All games are independent.

출력

For each integer q:

  • print one line with number s (0 ≤ s ≤ 1000) - required steps to produce the desired value.
  • In the next s lines, there should be 2 space-separated positive integers l and u, range bounds to produce the desired value.

제한

  • 1 ≤ T ≤ 1000
  • 1 ≤ q ≤ 1018

채점

There will be 10 test cases with T towers. For each test case, points will be calculated using the following rules:

  • If the solution produces the desired value with minimal number of steps for all towers, you get 10 points for the test case,
  • otherwise, your solution will be scored as the minimum of the score of all towers, where towers are scored as 1 + (minimum steps)/solution steps) · 7 rounded up to 2 decimal places.
  • If the solution for one of the towers is invalid, the solution gets 0 points.

All towers will have a valid solution.

예제 입력 1

3
2
3
7

예제 출력 1

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

In this example T = 3. Jernej wants to find out the required steps to get {2, 3, 7}. The current tower contains only one piece of paper with number [1].

The first desired value is 2.

In the first step, he can only make a sum of numbers from the range [1, 1], so the number on the next piece of paper can be only 1.

If Jernej wants to produce number 2, he should make a sum on the range [1, 2] (pick the 1st and 2nd number). This will sum into 2, which is the desired result.

The second desired value is 3. To produce 3, there are multiple ways. We can also produce 3 the following way:

1 1
1 2
2 3

채점

  • 예제는 채점하지 않는다.