How many solutions of the equation X1*X2+X2*X3+X3*X4+...+Xn-1*Xn=k Xi=0 or 1?
For example: when n = 3 and k = 0, the answer is 5. The solutions are {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0} and {1, 0, 1}.
Input
The input contains several test cases. The first line contains the number of the test cases. Eash of the following lines contains two numbers n and k, 2<=n<=1,000,000,000 0<=k<=40.
Output
For each test case, output one line contains the answer module 9973.