CA loves math.
In math class, the math teacher asks a question:
"How many 3-digit number which is multiple of 2 and the figures included do not repeat?"
CA thinks it's Too Simple, so he is thinking another harder question:
"How many number in $[1,A^n]$ which is multiple of $k$ and the figures included do not repeat(represented by A-ary)?"
Input
First line contains $T$ denoting the number of testcases.
$T$ testcases follow. Each testcase contains three intergers $A,n,k$ in one line.
$1 \le T \le 20,~2 \le A \le 11,~0 \le n \le 10^9,~1 \le k \le 10^9$
Output
For each testcase, output the answer in one line.
Sample Input
2
10 2 7
11 2 3
Sample Output
13
30
Hint
In the first testcase, the number which meet the conditions are {7,14,21,28,35,42,49,56,63,70,84,91,98}.
