Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sofia

Limits: 1s, 512 MB

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

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

Output

For each case, print the case number and followed by the number of possible unique paths.

Samples

InputOutput
3
2 3
5 7
9 1
Case 1: 3
Case 2: 210
Case 3: 1

Author
Discussion