Прилеглі біти#2445
Для рядка з бітів x_1, x_2, x_3, \ldots, x_n кількість пар сусідніх одиниць у рядку () задається як
тобто визначає, скільки разів одиничний біт стоїть поруч з іншим одиничним бітом. Наприклад:
\operatorname{AdjBC}(011101101) = 3,\ \operatorname{AdjBC}(111101101) = 4,\ \operatorname{AdjBC}(010101010) = 0
Напишіть програму, яка приймає на вхід цілі числа та і повертає кількість бітових рядків довжини (із 2^n), таких що \operatorname{AdjBC}(x) = k. Наприклад, для -бітних рядків існує способів отримати \operatorname{AdjBC}(x) = 2:
\mathbf{11100},\ \mathbf{01110},\ \mathbf{00111},\ \mathbf{10111},\ \mathbf{11101},\ \mathbf{11011}
Перший рядок містить одне ціле число (1 \leq P \leq 1000) — кількість наборів даних, що слідують далі. Кожен набір даних — це один рядок, що містить номер набору, пробіл, десяткове ціле число () — кількість бітів у рядках, пробіл і ще одне десяткове ціле () — бажане значення кількості сусідніх одиниць. Кількість бітів () не перевищує , а параметри і підібрані так, щоб результат поміщався у знакове -бітне ціле число.
Для кожного набору даних виведіть один рядок, що містить номер набору, пробіл і кількість -бітних рядків з кількістю сусідніх одиниць, що дорівнює .
Приклад 1