Interesting Integers#8345
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
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 and - 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 appears in the sequence that starts with 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?
First line contains the number of test cases, at most . After that per test case:
- one line with a single integer (2 \leq n \leq 10^9): the number to appear in the sequence.
For each test case print one line with two integers and (0 < a \leq b), such that, for G_1 = a and G_2 = b, G_k = n for some . 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.
Example 1