Problem D: Football Teams

Alice and Bob are playing football with their N friends and now they have to pick their teams by choosing players among their classmates. They will take turns and each time one of them will choose one or more of the remaining players. We can represent the order of their choices as a sequence of letters A (for Alice) and B (for Bob).

The two kids want to form teams of the same size, which means that a sequence should have the same exactly N/2 A’s and N/2 B’s. Being a gentleman, Bob will let Alice choose first, which means all valid sequences will start with an ’A’. Furthermore, at any given time in the process, Bob cannot have more players chosen than Alice, meaning that in any prefix of the sequence there will always be at least as many A’s as B’s. In order to make everything a little more balanced, they’ve also decided that they cannot choose more than K players consecutively.

The following are some examples of invalid sequences for 10 friends (N=10) and no more than 3 consecutive choices from the same kid (K=3):


ABBABABABA - invalid, because the prefix ABB has more B’s than A’s

AAABBBAABA - invalid, because there are 6 A’s and only 4 B’s

ABAAAABBBB - invalid, because there are 4 consecutive A’s (and also 4 consecutive B’s)


For the same scenario (N=10, K=3), these are examples of valid choices:


ABABABABAB

AABABBAABB

AAABBABBAB

AAABBBAABB

Note there are even more possible orders of choice. In fact, there are 34 different sequences representing valid choices for the case of N=10, K=3.

Now, if only they could know how many different ways are there for any possible case, they would be the heroes of their class... Can you help them?

Task

Given the number N of friends and the number K of maximum consecutive choices from the same kid, your task is to count in how many ways can the order of choices occur, that is, to count the number of different sequences representing valid scenarios as described before.

Input

The first line contains an integer T, the number of test cases to follow. Each of the following lines describes one case in the form Ni Ki, indicating respectively the number of friends and the maximum number of consecutive choices.

Output

The output should contain exactly T lines, each one giving the number of ways Wi in which the order of choices can occur for the respective case, as described before.

Constraints

1 ≤ T ≤ 100Number of test cases
2 ≤ Ni ≤ 100Number of friends (always an even number)
1 ≤ Ki ≤ N/2Number of consecutive choices from the same friend
1 ≤ Wi ≤ 1018Number of different orders of choice respecting the conditions

Input Example

6
10 3
10 4
8 2
12 6
20 5
24 10

Output Example

34
41
8
132
15107
207990
This document was translated from LATEX by HEVEA.