Recursive Queries

定义如下函数： $f(x)$ 为 $x$ 各位上非 $0$ 数字之积，$g(x)=\begin{cases}x&x<10\\g(f(x))&x\ge 10\end{cases}$ $Q$ 组询问。每问求使得 $g(x)=k$ 的 $x(x\in[l,r])$ 的个数。

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 $ .

The first line of the input contains an integer $ Q $ ( $ 1<=Q<=2×10^{5} $ ) representing the number of queries. $ Q $ lines follow, each of which contains 3 integers $ l $ , $ r $ and $ k $ $ (1<=l<=r<=10^{6},1<=k<=9) $ .

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

4
22 73 9
45 64 6
47 55 7
2 62 4

1
4
0
8

4
82 94 6
56 67 4
28 59 9
39 74 4

3
1
1
5

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 $