SPOJ in Gyumri

   The first question on the Data Structures and Algorithms final exam has a list of N  terms and a second list of N  definitions.  Students are to match each term with the correct definition.

   Unfortunately, Joe, who wrote a Visual BASIC program in high school and assumed he knew all there was to know about Computer Science, did not bother to come to class or read the textbook. He has to guess randomly what the matches are. Let S(N, k) be the number of ways Joe can answer the question and get at least the first k matches wrong.

   For this problem, you will write a program to compute S(N, k).

Input

   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 should be processed identically and independently.

   Each data set consists of a single line of input containing three space separated decimal integers. The first integer is the data set number. The second integer is the number, N (1 ≤ N ≤ 17), of terms to be matched in the question. The third integer is the number, k (0 ≤ k ≤ N ), of initial matches to be incorrect. 

Output

   For each data set there is a single line of output.  It contains the data set number followed by a single space which is then followed by the value of S(N, k).

Examples