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