Sofia has just arrived in Bangladesh. Rather asking it some dumb questions, lets give it a maze problem to solve.
Sofia is located at the top-left corner of a M x N grid (marked ‘Start’ in the diagram below).
It can only move either down or right at any point in time. It is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Above is a 3 x 7 grid
How many possible unique paths are there?
Sofia could not solve this problem (seems like it’s not that smart), as you are one of the best programmers in Bangladesh, you have been given this task to write code of this problem to help Sofia to be smarter.
Input starts with an integer T(<= 100) denoting the number of test cases. Each case starts with a line containing two integers M and N
Constraint : 1 <= M, N <= 25
For each case, print the case number and followed by the number of possible unique paths.
3 2 3 5 7 9 1
Case 1: 3 Case 2: 210 Case 3: 1