Interesting Integers

/problems/interestingintegers/file/statement/en/img-0001.png
source: xkcd.com/587

Undoubtedly you know of the Fibonacci numbers. Starting with $F_1 = 1$ and $F_2 = 1$, every next number is the sum of the two previous ones. This results in the sequence $1,1,2,3,5,8,13,\ldots $.

Now let us consider more generally sequences that obey the same recursion relation

\begin{equation*} G_ i = G_{i-1} + G_{i-2} \qquad \text {for } i>2 \end{equation*}

but start with two numbers $G_1 \leq G_2$ of our own choice. We shall call these Gabonacci sequences. For example, if one uses $G_1=1$ and $G_2=3$, one gets what are known as the Lucas numbers: $1,3,4,7,11,18,29,\ldots $. These numbers are – apart from $1$ and $3$ – different from the Fibonacci numbers.

By choosing the first two numbers appropriately, you can get any number you like to appear in the Gabonacci sequence. For example, the number $n$ appears in the sequence that starts with $1$ and $n-1$, but that is a bit lame. It would be more fun to start with numbers that are as small as possible, would you not agree?

Input

On the first line one positive number: the number of test cases, at most $100$. After that per test case:

  • one line with a single integer $n$ ($2 \leq n \leq 10^9$): the number to appear in the sequence.

Output

Per test case:

  • one line with two integers $a$ and $b$ ($0 < a \leq b$), such that, for $G_1=a$ and $G_2=b$, $G_ k = n$ for some $k$. These numbers should be the smallest possible, i.e., there should be no numbers $a’$ and $b’$ with the same property, for which $b’<b$, or for which $b’=b$ and $a’<a$.

Sample Input 1 Sample Output 1
5
89
123
1000
1573655
842831057
1 1
1 3
2 10
985 1971
2 7