提示: 欢迎访问OurACM平台。
Problem 1816 Kakuro

Accept: 12    Submit: 17
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Kakuro puzzles resemble crosswords which use numbers instead of words. The aim of the game is to fill all the blank squares in the grid with only the numbers 1-9 so that the numbers you enter add up to the corresponding clues. Furthermore, you may not use a number more than once in the sum for any clue. For example, if you must make 11 using 4 numbers, there is a unique solution: 1+2+3+5 = 11. These numbers need not be placed from smallest to largest, of course.

As an example, look at the following board:

Rather than solving an entire board, your problem is simpler. Given the number that you must sum to, the maximum value of the numbers that can be used in the sum, and the number of squares to be used to make the sum, find the number of distinct solutions. A solution is distinct from another solution if they cannot be obtained from one another by permutation.

Input

The first line of input consists of the number of test cases T ≤ 100 on a line by itself. Each of the next T lines will contain 3 white space separated integers C, M and S, where C is the number of squares to be used in the sum, M ≤ 100 is the maximum number that can be used in any square, and S is the sum to be made. No bounds are given on C or S, except that they can be stored into unsigned integers.

Output

For each test case, print the number of valid solutions on a line by itself. The solution is guaranteed to fit within a 64-bit signed integer.

Sample Input

1 5 9 16

Sample Output

1

Source

2008-2009 North-America North-East Preliminary

Submit  Back  Status  Discuss