Безсумнівно, ви знаєте числа Фібоначчі. Починаючи з 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.