Xunayed is furious. He found out that his friend Nurulla who is just like his brother (tore ami bae bhabsilam), did some gutibazi with him. Xunayed can forgive anything, but gutibazi is something he can never forgive. But to give Nurulla a lesson Xunayed first has to go to Nurulla through some path. Then the problem occurs. Roads belong to a very powerful individual named Rizvi and everyone has to take permission from him to pass those roads. Rizvi will give permission to Xunayed only if Xunayed can solve a riddle.

Path is some 2d grid. Xunayed is currently on upper left cell (cell (1,1) in the figure below) which is source. Nurulla is now on lower right cell (cell (3,3) in the figure below) which is destination. Xunayed can only go down/right from his current cell. In how many ways there exists a path where Xunayed can reach Nurulla.

Solve this riddle to help innocent Xunayed and bring forth justice.

Input

Input starts with an integer T (<= 50), denoting the number of test cases.

Each case starts with a line containing two integers R C (1 <= R, C <= 7), where R denotes the number of rows and C denotes the number of columns of the grid respectively.

Output

For every test case, output an integer which represents the number of ways Xunayed can reach Nurulla.

Example

Input:
2
1 1
2 2

Output:
1
2