Интересные числа
Несомненно, вы знаете числа Фибоначчи. Начиная с F[1] = 1 и F[2] = 1, каждое следующее число представляет собой сумму двух предыдущих. Это приводит к последовательности 1, 1, 2, 3, 5, 8, 13, ... . Теперь рассмотрим более общие последовательности, которые подчиняются одному и тому же рекуррентному соотношению
G[i] = G[i-1] + G[i-2] для i > 2
но начнем с двух чисел G[1] ≤ G[2] по собственному выбору. Назовем эти последовательности Габоначчи. Например, если взять G[1] = 1 и G[2] = 3, можно получить числа Люка: 1, 3, 4, 7, 11, 18, 29, ... . Все эти числа - кроме 1 и 3 - отличаются от чисел Фибоначчи.
Выбирая определенным образом первые два числа, Вы можете получить любое число в последовательности Габоначчи. Например, число n появится в последовательности, начинающейся с 1 и n - 1, но это решение не оптимально. Было бы интересно найти наименьшие числа, с которых можно было бы начать последовательность.
Входные данные
Первая строка содержит количество тестов, не более 100. Далее для каждого теста:
одна строка содержит одно целое число n (2 ≤ n ≤
10^9): число, появляющееся в последовательности.
Выходные данные
Для каждого теста выведите в отдельной строке два целых числа a и b (0 < a ≤ b) такие что для G[1] = a и G[2] = b, G[k] = n для некоторого k. Эти числа должны быть как можно меньшими, то есть не должно существовать таких a' и b' с таким же свойством, для которых b' < b, или для которых b' = b и a' < a.