让我们在正整数上定义两个函数 f 和 g。
$$f(n) = \text{非零数字的乘积 } n$$$${ g ( n ) = { \begin{cases} n & \quad { \mathrm { i f ~ } } n < 10 \\ g ( f ( n ) ) & \quad { \mathrm { o t h e r w i s e } } \end{cases} } }$$
您需要处理 Q 查询。在每个查询中,您将获得三个整数 l、r 和 k。您需要打印 l 和 r 之间的整数 x 的数量,使得 g(x) = k。
输入
输入的第一行包含一个整数 Q (1 ≤ Q ≤ 2 × 105),表示查询数量。
接下来是 Q 行,每行包含 3 个整数 l、r 和 k (1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9)。
输出
对于每个查询,打印包含该查询答案的一行。
示例
输入 #1
4 22 73 9 45 64 6 47 55 7 2 62 4
输出 #1
1 4 0 8
输入 #2
4 82 94 6 56 67 4 28 59 9 39 74 4
输出 #2
3 1 1 5
注意
在第一个示例中:
- g(33) = 9 为 g(33) = g(3 × 3) = g(9) = 9
- g(47) = g(48) = g(60) = g(61) = 6
- 47 到 55 之间没有这样的整数。
- g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4