Problem Description

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.

2
10 2 7
11 2 3

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}.