题目描述

对于一个由n位二进制位组成的字符串 ( x_1, x_2, x_3, \dots, x_n )，其相邻位计数（AdjBC(x)）定义为：
[ x_1x_2 + x_2x_3 + x_3x_4 + \dots + x_{n-1}x_n ]
该值表示字符串中相邻两个1的对数。例如：

• AdjBC(011101101) = 3
• AdjBC(111101101) = 4
• AdjBC(010101010) = 0

编写一个程序，输入整数n和k，输出满足AdjBC(x) = k的n位二进制字符串的数量（共(2^n)种可能的字符串）。例如，对于5位字符串，满足AdjBC(x)=2的字符串有6种：
11100, 01110, 00111, 10111, 11101, 11011

输入

输入第一行包含一个整数P（(1 \leq P \leq 1000)），表示测试用例的数量。
每个测试用例占一行，包含三个部分：测试用例编号、整数n（二进制字符串的位数）、整数k（目标相邻位计数值）。
数据保证n不超过100，且n和k的取值使得结果可以用32位有符号整数表示。

输出

对于每个测试用例，输出一行，格式为：测试用例编号 + 空格 + 满足条件的n位二进制字符串数量。

输入示例1

10  
1 5 2  
2 20 8  
3 30 17  
4 40 24  
5 50 37  
6 60 52  
7 70 59  
8 80 73  
9 90 84  
10 100 90  

输出示例1

1 6  
2 63426  
3 1861225  
4 168212501  
5 44874764  
6 160916  
7 22937308  
8 99167  
9 15476  
10 23076518  

来源

Greater New York Regional 2009