Your childhood gaming hero Mario sets about his journey to save Princess Peach from the army of turtles. You need to use your programming skills to save him from certain precarious situations.

In the very first level he is encountered with a chessboard (may not necessarily be a square one). Each square of the chess board has a number of turtles present on it. Instead of directly starting to move, Mario thinks of finding a proper a strategy so as to avoid most turtles. You don't need to find that strategy. You just need to tell him the number of turtles in any square.

The number of turtles in any square follow a particular sequence:

• N(n, k) is the number, where n and k are coordinates of the square.
• N(n, 0) = n, for all positive n.
• N(n, k) = N(1, k-1) + N(2, k-1) + ... + N(n, k-1), for all positive k, n.

Given k and n, find the value for N(n, k).

Input

The first line contains the number of test cases T (T ≤ 120). The next T lines contain two integers, n and k (n, k ≤ 20).

Output

T lines containing output for N(n, k)

Example

Input:
3
4 0
3 1
3 5

Output:
4
6
28