#1222 Tree Planting

42  1 s   128 MB  

Description

 A farmer wants to plant a row of trees along the front of his house. He has two different kinds of trees, some which are plain looking, and other, more expensive, fancy trees. He wishes to plant the trees in such a way that not all of the fancy trees are grouped together, so he insists that no two fancy trees be adjacent to one another.
You are given an int total indicating the total number of trees to be planted, and an int fancy which is the number of fancy trees. You are to calculate a long indicating the number of possible tree arrangements that meet the farmer's criteria of having no two fancy trees adjacent to one another.
Notes
- You may assume that each fancy tree is identical to one other, and likewise for the plain trees.
- If no valid arrangements are possible, the output should be 0.

Input

The first line contains the number of test cases T (T ≤ 1,000).
Each of the following T lines contains two integers total(1 ≤ total ≤ 60) and fancy(1 ≤ fancy ≤ total) as a test case.

Output

Output the answer of each test case on a separate line.

Sample Input

Sample Output

4
4 2
3 1
4 3
10 4
3
3
0
35