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, ... . Now let us consider more generally sequences that obey the same recursion relation
G[i] = G[i-1] + G[i-2] for i > 2
but start with two numbers G[1] ≤ 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, ... . 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
First line contains the number of test cases, at most 100. After that per test case:
one line with a single integer n (2 ≤ n ≤
10^9): the number to appear in the sequence.
Output
For each test case print one line with two integers a and b (0 < a ≤ 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.