eolymp
bolt
Try our new interface for solving problems
Məsələlər

Задача A + B

Задача A + B

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

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

Giriş verilənləri

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

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
1 2
2 2 4
3 2 4 6
2 2 5
Çıxış verilənləri #1
Case 1:
1 5
Case 2:
2 5 7