Problem D
Interesting Integers
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 |
