Counting Valid Sequences

You are given three integers n, k, and target. Your task is to count the number of valid sequences of length n where each element is an integer between 1 and k (inclusive) and the sum of the sequence is exactly target.

This problem can be solved using dynamic programming. Define a DP table \(dp[i][s]\) which represents the number of ways to form a sum \(s\) using exactly \(i\) numbers. The recurrence relation is given by:

[ dp[i][s] = \sum_{num=1}^{k}{dp[i-1][s-num]} \quad \text{for } s \geq num, ]

with the base case \(dp[0][0]=1\) (there is one way to have a sum of 0 using 0 numbers) and \(dp[0][s]=0\) for \(s > 0\).

Implement a solution that reads the input from standard input and writes the output to standard output.

inputFormat

The first line of the input contains a single integer T representing the number of test cases. Each of the following T lines contains three integers n, k, and target separated by spaces.

For example:

2
3 2 4
2 3 5

outputFormat

For each test case, output a single line containing the number of valid sequences that can be formed.

For the sample input above, the expected output is:

3
2

## sample

2
3 2 4
2 3 5

3
2

</p>