题目描述

Now Alice wants to sum up all integers whose digit sum is exactly $a^b$.

However we all know the number of this kind of integers are unlimited. So she decides to sum up all these numbers

whose each digit is non-zero.

Since the answer could be large, she only needs the remainder when the answer divided by a given integer $p$.

输入格式

The input has several test cases and the first line contains the integer $t (1 \le t \le 400)$ which is the number of test cases.

For each test case, a line consisting of three integers $a, b (1 \le a, b \le 20)$ and $p (2 \le p \le 10^9)$ describes the restriction of the digit sum and the given integer $p$.

输出格式

For each test case, output a line with the required answer.

Here we provide an explanation of the following sample output. All integers satisfying the restriction in the input are $4, 13, 31, 22, 121, 112, 211$ and $1111$. The sum of them all is $4 + 13 + 31 + 22 + 121 + 112 + 211 + 1111 = 1625$ and that is exactly the sample output.

5
2 1 1000000
3 1 1000000
2 2 1000000
3 3 1000000
10 1 1000000

13
147
1625
877377
935943