# Number of Unique Paths

Given a **M X N matrix** with initial position at top-left cell, **find the number of possible unique paths to reach the bottom right cell of the matrix from the initial position**. Possible moves can be either **down** or **right** at any point in time.

Input:
The first line contains an integer T,
depicting total number of test cases.
Then following T lines contains two integers
m and n depicting the size of the grid.
Output:
Print the number of unique paths to reach
bottom-right cell from the top-left cell.

**Example with explanation:**

Input:
2
3 3
3 4
Output:
6
10

So, for the first test case, **M=3, n=3**

Grid is like,

1. (0,0)->(0,1)->(0,2)->(1,2)->(2,2)

2. (0,0)->(0,1)->(1,1)->(1,2)->(2,2)

3. (0,0)->(0,1)->(1,1)->(2,1)->(2,2)

4. (0,0)->(1,0)->(2,0)->(2,1)->(2,2)

5. (0,0)->(1,0)->(1,1)->(1,2)->(2,2)

6. (0,0)->(1,0)->(1,1)->(2,1)->(2,2)

**This are the possible unique paths and hence count is 6.**

Given a matrix with an initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position. Possible moves can be either or at any point in time.

Recursion Algorithm:So, the algorithm can be:

But this would generate many overlapping subproblems, which will be computed again and again increasing the time complexity. Hence, we can convert the recursion to dynamic Programming.

Dynamic Programming approach:C++ Implementation:Output