22743_TheRascalTriangle

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

R ( n , m ) = 0   for  n < 0  OR  m < 0   OR  m > n

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

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

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

R ( n+1 , m+1 ) = ( R ( n , m ) * R ( n , m+1 ) + 1 ) / R ( n-1 , m )

1
1   1
 1   2   1
 1   3   3   1
 1   4   5   4   1

Write a program which computes R( n, m ) the m-th element of the n-th row of the Rascal Triangle.

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

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

5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398

1 1
2 5
3 411495886
4 24383845
5 264080263