← 返回题目列表

Codeforces · 932/B

B. 递归查询

中文机器翻译题面 查看原题

让我们在正整数上定义两个函数 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