题目描述

现在 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$，这恰好是样例输出之一。

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

13
147
1625
877377
935943

提示

翻译由 DeepSeek V4 Pro 完成