设 $$$D(n)$$$ 表示 $$$n$$$ 的数字之和。对于多少个整数 $$$n$$$,其中 $$$10^{l} \leq n < 10^{r}$$$ 满足 $$$D(k \cdot n) = k \cdot D(n)$$$?输出对 $$$10^9+7$$$ 取模的答案。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – 测试用例的数量。
每个测试用例包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$0 \leq l < r \leq 10^9$$$、$$$1 \leq k \leq 10^9$$$)。
输出
对于每个测试用例,输出一个整数,即答案,模 $$$10^9 + 7$$$。
示例
输入 #1
6 0 1 4 0 2 7 1 2 1 1 2 3 582 74663 3 0 3 1
输出 #1
2 3 90 12 974995667 999
注意
对于第一个测试用例,满足条件的 $$$n$$$ 的唯一值是 $$$1$$$ 和 $$$2$$$。
对于第二个测试用例,满足条件的 $$$n$$$ 的唯一值是 $$$1$$$、$$$10$$$ 和 $$$11$$$。
对于第三个测试用例,$$$n$$$ 之间的所有值(包括 $$$10$$$ 和 $$$100$$$ 除外)都满足条件。