Задача A + B#1729

Задача A + B

1 секунда

64 мегабайти

Середня

Ви знаєте про відомий ряд Фібоначчі? Він визначається рекурентним співвідношенням:

$F_{0} = 0$ F_0 = 0, $F_{1} = 1$ F_1 = 1, і $F_{n} = F_{n - 1} + F_{n - 2}$ F_n = F_{n-1} + F_{n-2} для $n \geq 2$ n \geq 2.

Числа Фібоначчі мають багато цікавих властивостей. Одна з них полягає в тому, що числа Фібоначчі можна використовувати для представлення цілих чисел. Кожне додатне ціле число можна єдиним чином подати у вигляді

$n = F_{k_{1}} + F_{k_{2}} + \dots + F_{k_{m}}$ n = F_{k_1} + F_{k_2} + \ldots + F_{k_m}, де $k_{i} \geq k_{i - 1} + 2$ k_i \geq k_{i-1} + 2 для $2 \leq i \leq m$ 2 \leq i \leq m, і $k_{1} \geq 2$ k_1 \geq 2.

Наприклад, $6$ можна подати як $F_{2} + F_{5}$ F_2 + F_5, а $12$ як $F_{2} + F_{4} + F_{6}$ F_2 + F_4 + F_6.

Тепер, коли ви знаєте, як подавати додатні цілі числа за допомогою чисел Фібоначчі, чи зможете ви їх додавати? Вам дано два додатні цілі числа, кожне з яких подане у вигляді суми різних, не сусідніх чисел Фібоначчі. Ваше завдання — знайти їхню суму, подану у такому ж вигляді.

Вхідні дані

Перший рядок містить одне ціле число $T$ — кількість тестів.

Кожен тест складається з двох рядків. Кожен рядок містить одне ціле число $m$ , а також $m$ цілих чисел $k_{1}, k_{2}, \dots, k_{m}$ k_1, k_2, \ldots, k_m, що означає подання додатного числа у вигляді $F_{k_{1}} + F_{k_{2}} + \dots + F_{k_{m}}$ F_{k_1} + F_{k_2} + \ldots + F_{k_m}.

Гарантується, що вхідні дані коректні. $1 \leq T \leq 100$ 1 \leq T \leq 100, $1 \leq m \leq 100$ 1 \leq m \leq 100, $2 \leq k_{i} \leq 1000000$ 2 \leq k_i \leq 1000000.

Вихідні дані

Для кожного тесту спочатку виведіть номер тесту, а потім у наступному рядку — суму двох заданих чисел, подану як суму різних, не сусідніх чисел Фібоначчі, у такому ж форматі, як і вхідні дані.

Приклади

Приклад 1