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)?"
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$
For each testcase, output the answer in one line.