Exact Step Grid Paths

You are given a grid with n rows and m columns. Your task is to determine the number of unique paths from the top-left corner to the bottom-right corner if you can only move either down or right, and you must take exactly (k) steps. Note that the minimum number of steps required to go from the top-left to the bottom-right in an (n \times m) grid is (n+m-2). Therefore, a valid path exists if and only if (k = n+m-2). In this case, the number of unique paths is given by the binomial coefficient: [ \binom{n+m-2}{n-1} = \frac{(n+m-2)!}{(n-1)!,(m-1)!} ] If (k \neq n+m-2), then there is no valid path and the output should be 0.

Input / Output Format:

• Input: The first line contains an integer \(T\), the number of test cases. Each of the next \(T\) lines contains three integers \(n\), \(m\), and \(k\) separated by spaces.
• Output: For each test case, output a single integer representing the number of valid paths.

Input:
3
2 2 2
3 3 4
4 4 6
Output:
2
6
20

inputFormat

The first line contains an integer (T) denoting the number of test cases. Each subsequent line contains three space-separated integers (n) (number of rows), (m) (number of columns), and (k) (required number of steps).

outputFormat

For each test case, output a single line containing one integer: the number of distinct paths from the top-left corner to the bottom-right corner that use exactly (k) steps. If no such path exists, output 0.## sample

3
2 2 2
3 3 4
4 4 6

2
6
20