Undoubtedly you know of the Fibonacci numbers. Starting with F1 = 1 and F2 = 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

Gi = Gi-1 + Gi-2 for i > 2

but start with two numbers G1 ≤ G2 of our own choice. We shall call these Gabonacci sequences. For example, if one uses G1 = 1 and G2 = 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 ≤ 109): 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 G1 = a and G2 = b, Gk = 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.