Прилеглі біти
Для рядка з n бітів x_1, x_2, x_3, …, x_n, визначимо функцію суміжних бітів (AdjBC(x)) як:
x_1·x_2 + x_2·x_3 + x_3·x_4 + … + x_{n-1}·x_n
Ця функція підраховує, скільки разів біт 1 прилягає до іншого біта 1. Наприклад:
AdjBC(011101101) = 3 AdjBC(111101101) = 4 AdjBC(010101010) = 0
Напишіть програму, яка приймає на вхід числа n і k та повертає кількість n-бітних рядків (з 2^n), які задовольняють умову AdjBC(x) = k. Наприклад, для 5-бітних рядків існує шість способів отримати AdjBC(x) = 2:
11100, 01110, 00111, 10111, 11101, 11011
Вхідні дані
Перша строка вхідного файлу містить одне ціле число P (1 ≤ P ≤ 1000), яке вказує на кількість наступних наборів даних. Кожен набір даних представлений одним рядком, що містить номер набору даних, потім пробіл, а далі задане десяткове ціле число (n) біт у n-бітному рядку, за яким слідує ще один пробіл і далі десяткове число (k) для підрахунку прилеглих бітів. Кількість біт (n) не перевищує 100, і значення n та k підібрані так, що відповідь вміщується в 32-розрядне число.
Вихідні дані
Для кожного набору вхідних даних виведіть один рядок. Він повинен містити номер тестового набору даних, за яким слідує один пробіл, а потім кількість n-бітних рядків, для яких кількість суміжних одиничних бітів дорівнює k.