CF932B.Recursive Queries

Let us define two functions f and g on positive integer numbers.

You need to process Q queries. In each query, you will be given three integers l, r and k. You need to print the number of integers x between l and r inclusive, such that g(x) = k.

我们定义两个在正整数上的函数 $f$ 和 $g$：

你需要处理 $Q$ 个查询。在每个查询中，你将获得三个整数 $l$、$r$ 和 $k$。你需要输出满足 $g(x) = k$ 的整数 $x$ 的个数，其中 $x$ 在区间 $[l, r]$ 内（含端点）。

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 105) representing the number of queries.

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9).

输入的第一行包含一个整数 $Q$（$1 \leq Q \leq 2 \times 10^5$），表示查询次数。

接下来有 $Q$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \leq l \leq r \leq 10^6$，$1 \leq k \leq 9$）。

For each query, print a single line containing the answer for that query.

对于每个查询，输出一行，包含该查询的答案。

In the first example:

• g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9
• g(47) = g(48) = g(60) = g(61) = 6
• There are no such integers between 47 and 55.
• g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4

在第一个例子中：

• $g(33) = 9$，因为 $g(33) = g(3 \times 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$