eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Задача A + B

Задача A + B

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Знаете ли вы известную последовательность Фибоначчи? Она определяется рекуррентно следующим образом:

F_0 = 0, F_1 = 1 и F_n = F_{n-1} + F_{n-2} для n2.

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

n = F_k1 + F_k2 + … + F_km, k_ik_{i -1} + 2 для 2im и k_12

Например, 6 можно представить в виде F_2+F_5, а 12 может быть представлено ​​в виде F_2+F_4+F_6.

Теперь вы знаете, как представлять натуральные числа при помощи чисел Фибоначчи, но сможете ли Вы сложить их? Заданы два натуральных числа, сформированных при помощи чисел Фибоначчи. Ваша задача вычислить их сумму.

Входные данные

Первая строка содержит одно целое число T, указывающее на количество тестовых случаев.

Каждый тестовый случай состоит из двух строк, каждая строка содержит целое число m, за которым следует m целых чисел k_1, k_2, …, k_m,_{ }указывающих на способ формирования целого числа при помощи чисел Фибоначчи F_k1+F_k2+…+F_km.

Корректность входных данных гарантируется. 1T100, 1m100, 2k_i1000000.

Выходные данные

Для каждого тестового случая выведите сначала номер тестового случая, а затем в следующей строке укажите сумму двух заданных чисел, также сформированную, как и во входных данных, при помощи чисел Фибоначчи.

Пример

Входные данные #1
2
1 2
2 2 4
3 2 4 6
2 2 5
Выходные данные #1
Case 1:
1 5
Case 2:
2 5 7