Цікаві числа#8345

Цікаві числа

1 секунда

64 мегабайти

Дуже легка

Безсумнівно, ви знаєте числа Фібоначчі. Починаючи з $F_{1} = 1$ F_1 = 1 і $F_{2} = 1$ F_2 = 1, кожне наступне число дорівнює сумі двох попередніх. Це призводить до послідовності $1, 1, 2, 3, 5, 8, 13, \dots$ 1, 1, 2, 3, 5, 8, 13, \ldots. Тепер розглянемо загальніші послідовності, які також підкоряються цьому рекурентному співвідношенню:

G_{i} = G_{i - 1} + G_{i - 2} для i > 2

G_i = G_{i-1} + G_{i-2} \quad\text{для}\ i > 2

але починаються з двох чисел $G_{1} \leq G_{2}$ G_1 \leq G_2 на власний вибір. Назвемо ці послідовності габоначчі. Наприклад, якщо взяти $G_{1} = 1$ G_1 = 1, $G_{2} = 3$ G_2 = 3, отримаємо числа Люка: $1, 3, 4, 7, 11, 18, 29, \dots$ 1, 3, 4, 7, 11, 18, 29, \ldots. Всі ці числа, окрім $1$ і $3$ , відрізняються від чисел Фібоначчі.

Вибираючи певним чином перші два числа, ви можете отримати будь-яке число у послідовності габоначчі. Наприклад, $n$ з'явиться у послідовності, що починається із $1$ та $n - 1$ n-1, але це рішення не є оптимальним. Було б цікаво знайти найменші числа, з яких можна почати таку послідовність.

Вхідні дані

Перший рядок містить кількість тестів, не більше $100$ . Далі для кожного тесту:

один рядок містить одне ціле число $n$ ( $2 \leq n \leq 1 0^{9}$ 2 \leq n \leq 10^9): число, яке зустрічається у послідовності.

Вихідні дані

Для кожного тесту виведіть в окремому рядку два цілих числа $a$ і $b$ ( $0 < a \leq b$ 0 < a \leq b) такі, що для $G_{1} = a$ G_1 = a, $G_{2} = b$ G_2 = b виконується $G_{k} = n$ G_k = n для деякого $k$ . Ці числа повинні бути мінімальними, тобто не існує таких $a^{'}, b^{'}$ a', b' із цією ж властивістю, що $b^{'} < b$ b' < b, або $b^{'} = b$ b' = b і $a^{'} < a$ a' < a.

Приклади

Приклад 1