Let us define two functions f and g on positive integer numbers.  $f(n) = \text{product of non-zero digits of} n$
$g(n) = \left\{\begin{array}{ll}{n} & {\text{if} n < 10} \\{g(f(n))} & {\text{otherwise}} \end{array} \right.$ 
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. 
-----Input-----
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).
-----Output-----
For each query, print a single line containing the answer for that query.
-----Examples-----
Input
4
22 73 9
45 64 6
47 55 7
2 62 4
Output
1
4
0
8
Input
4
82 94 6
56 67 4
28 59 9
39 74 4
Output
3
1
1
5
-----Note-----
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
# -*- coding: utf-8 -*-

# Baqir Khan
# Software Engineer (Backend)

import bisect as b
from sys import stdin

inp = stdin.readline

pre_calc = x = [[] for i in range(10)]


def get_g(num):
    while num > 9:
        new_num = 1
        while num:
            digit = num % 10
            if digit:
                new_num *= digit
            num //= 10
        num = new_num
    return num


for i in range(1, 10 ** 6 + 5):
    pre_calc[get_g(i)].append(i)

q = int(inp())

while q:
    q -= 1
    l, r, x = list(map(int, inp().split()))
    index_l = b.bisect_left(pre_calc[x], l)
    if index_l < len(pre_calc[x]) and pre_calc[x][index_l] >= l:
        index_l -= 1
    index_r = b.bisect_left(pre_calc[x], r)
    if index_r < len(pre_calc[x]) and pre_calc[x][index_r] <= r:
        index_r += 1
    print(max(index_r - index_l - 1, 0))

# -*- coding: utf-8 -*-

# Baqir Khan
# Software Engineer (Backend)

import bisect as b
from sys import stdin

inp = stdin.readline

pre_calc = x = [[] for i in range(10)]


def get_g(num):
    while num > 9:
        new_num = 1
        while num:
            digit = num % 10
            if digit:
                new_num *= digit
            num //= 10
        num = new_num
    return num


for i in range(1, 10 ** 6 + 5):
    pre_calc[get_g(i)].append(i)

q = int(inp())

while q:
    q -= 1
    l, r, x = list(map(int, inp().split()))
    index_l = b.bisect_left(pre_calc[x], l)
    if index_l < len(pre_calc[x]) and pre_calc[x][index_l] >= l:
        index_l -= 1
    index_r = b.bisect_left(pre_calc[x], r)
    if index_r < len(pre_calc[x]) and pre_calc[x][index_r] <= r:
        index_r += 1
    print(max(index_r - index_l - 1, 0))
