NUMPATH - Gutibazi

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.

grid

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

Added by:imranziad
Date:2016-03-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:IAPC (Rawnak Sarker)

hide comments
2018-07-01 08:12:05
DP :)
2018-06-07 10:31:54
easy problem....just derive a general formula using P&C,
costed me 4-5 WA by just silly mistakes... :)
2017-02-18 19:42:04
tutorial problem...
2016-10-22 08:23:06
very easy problem.. AC in a go...tutorial stuff ;)
2016-06-19 03:35:42 Piyush Kumar
Should be moved to tutorial!
2016-04-16 19:00:44 Akshat Jain
very easy...can also be done without dp...simple permutation and combination logic
2016-04-03 02:35:33 pk
Cake walk!
2016-03-30 23:11:02 Umesh Malhotra
Very easy dp problem
2016-03-30 20:05:54
question is not clear!
2016-03-25 11:22:24 Mihajlo
ez dp ac in 1st go :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.