Прилегающие биты
Для строки из 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 и возвращает количество x 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.