CA Loves Math

Accepts: 0
Submissions: 53
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)
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.
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}.