SPOJ in Gyumri

        Undoubtedly you know of the Fibonacci numbers. Starting with F₁ = 1 and F₂ = 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₁ ≤ G₂ of our own choice. We shall call these Gabonacci sequences. For example, if one uses G₁ = 1 and G₂ = 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

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 ≤ n ≤ 10⁹): the number to appear in the sequence.

Output

Per test case:

• one line with two integers a and b (0 < a ≤ b), such that, for G₁ = a and G₂ = b, G_k = n for some k. These numbers should be the smallest possible, i.e., there should be no numbers a^t and b^t with the same property, for which b^t < b, or for which b^t = b and a^t < a.

Examples