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

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.

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$