G. D-函数

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $256$ 兆字节

设 $D(n)$ 表示 $n$ 的各位数字之和。对于多少个整数 $n$ 满足 $10^{l} \le n < 10^{r}$ 且 $D(k \cdot n) = k \cdot D(n)$？输出答案对 $10^{9}+7$ 取模。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^{4}$）——测试用例的数量。

每个测试用例包含三个整数 $l$、$r$ 和 $k$（$0 \le l < r \le 10^{9}$，$1 \le k \le 10^{9}$）。

输出

对于每个测试用例，输出一个整数，即满足条件的 $n$ 的个数，对 $10^{9}+7$ 取模。

示例

输入

6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1

输出

2
3
90
12
974995667
999

注

• 在第一个测试用例中，满足条件的 $n$ 只有 $1$ 和 $2$。
• 在第二个测试用例中，满足条件的 $n$ 只有 $1$、$10$ 和 $11$。
• 在第三个测试用例中，所有满足 $10 \le n < 100$ 的 $n$ 都满足条件。