Number of steps in Euclidean Algorithm

This problem was created by Mathias Kern aka gardengnome - many thanks!

In the Euclidean algorithm, two integers x and y with x>=y are replaced with y and x mod y until y becomes 0. For example:

• (x, y) = (9, 7) is replaced with (7, 2),
• which then is replaced with (2, 1),
• which then is replace with (1, 0), and the algorithm terminates.

Overall, the algorithm took three steps.

Your task is to find integer pairs for which the Euclidean algorithm runs exactly n steps.

Input: The first line contains the number t of test cases.
The second line contains t integer values – each is the count of target steps for the Euclidean algorithm.

Output: A single line of t space-separated integer pairs x and y with x >= y >=1 so that the Euclidean algorithm for the i-th pair takes exactly the i-th target number of steps.

Example:

input:
2
1 3

answer:
111 111 9 7