For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one . The first few integers in this class are . Denote  as the -th smallest integer in this class. To make it even larger, we consider integers in the form of . Now, given a prime number , how many pairs  are there such that .

The input contains multiple cases. The first line of the input contains a single integer , the number of cases.
For each case, the input consists of a single line, which contains 3 positive integers .

Print the answer, a single integer, in one separate line for each case.

2
11 8 1
7 6 2

4
2