## 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