Alice 想要将所有数位之和恰好为 $a^b$ 的整数求和。 然而我们都知道这类整数有无穷多个。因此，她决定只对那些每一位数字都不为零的整数进行求和。 由于答案可能非常大，她只需要求出答案除以给定整数 $p$ 后的余数。

输入格式

输入包含多组测试数据，第一行包含一个整数 $t$ ($1 \le t \le 400$)，表示测试数据的组数。 对于每组测试数据，输入一行包含三个整数 $a, b$ ($1 \le a, b \le 20$) 和 $p$ ($2 \le p \le 10^9$)，描述了数位之和的限制以及给定的整数 $p$。

输出格式

对于每组测试数据，输出一行，包含所需的答案。

这里我们对样例输出进行解释。所有满足输入限制的整数为 4, 13, 31, 22, 121, 112, 211 和 1111。它们的总和为 $4 + 13 + 31 + 22 + 121 + 112 + 211 + 1111 = 1625$，这正是样例输出的结果。

样例

样例输入 1

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

样例输出 1

13
147
1625
877377
935943