The Rascal Triangle#3552
Sign in

The Rascal Triangle

1 second
64 megabytes
Medium

The Rascal Triangle definition is similar to that of the Pascal Triangle. The rows are numbered from the top starting with . Each row contains n+1 numbers indexed from to . Using R(n,m) to indicate the index item in the index row:

R(n,m) = 0 \text{ for } n < 0 \text{ OR } m < 0 \text{ OR } m > n

The first and last numbers in each row (which are the same in the top row) are :

R(n,0) = R(n,n) = 1

The interior values are determined by (UpLeftEntry \cdot UpRightEntry+1)/UpEntry (see the parallelogram in the array below):

R(n+1, m+1) = (R(n,m) \cdot R(n,m+1) + 1)/R(n-1,m)

Write a program which computes R(n,m), the element of row at index in the Rascal Triangle.

Input

The first line of input contains a single integer (1 \le P \le 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of space separated decimal integers. The first integer is data set number, . The second integer is row number , and the third integer is the index within the row of the entry for which you are to find R(n,m) the Rascal Triangle entry (0 \le m \le n \le 50000).

Output

For each data set there is one line of output. It contains the data set number , followed by a single space which is then followed by the Rascal Triangle entry R(n,m) rounded to the integer value.

Examples

Example 1

Loading
Loading