Несомненно, вы знаете числа Фибоначчи. Начиная с F1 = 1 и F2 = 1, каждое следующее число представляет собой сумму двух предыдущих. Это приводит к последовательности 1, 1, 2, 3, 5, 8, 13, ... . Теперь рассмотрим более общие последовательности, которые подчиняются одному и тому же рекуррентному соотношению

Gi = Gi-1 + Gi-2 для i > 2

но начнем с двух чисел G1 ≤ G2 по собственному выбору. Назовем эти последовательности Габоначчи. Например, если взять G1 = 1 и G2 = 3, можно получить числа Люка: 1, 3, 4, 7, 11, 18, 29, ... . Все эти числа - кроме 1 и 3 - отличаются от чисел Фибоначчи.

Выбирая определенным образом первые два числа, Вы можете получить любое число в последовательности Габоначчи. Например, число n появится в последовательности, начинающейся с 1 и n - 1, но это решение не оптимально. Было бы интересно найти наименьшие числа, с которых можно было бы начать последовательность.

Входные данные

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

• одна строка содержит одно целое число n (2 ≤ n ≤ 109): число, появляющееся в последовательности.

Выходные данные

Для каждого теста выведите в отдельной строке два целых числа a и b (0 < a ≤ b) такие что для G1 = a и G2 = b, Gk = n для некоторого k. Эти числа должны быть как можно меньшими, то есть не должно существовать таких a' и b' с таким же свойством, для которых b' < b, или для которых b' = b и a' < a.