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 sqaure one). Each sqaure 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
first line contains number of test cases T
the next T lines (T <= 120) contain two integers, n and k (n , k <= 20)

Output
T lines containing output for N(n,k)

Sample I/O
Input
3
4 0
3 1
3 5

Output
4
6
28