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

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/120df92771639f1f51a4b216dccd3ed7c32bb859.png" style="max-width: 100.0%;max-height: 100.0%;"/> 

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<sup class="upper-index">5</sup>) representing the number of queries. 

*Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1 ≤ *l* ≤ *r* ≤ 10<sup class="upper-index">6</sup>, 1 ≤ *k* ≤ 9).
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
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
'''
11/10/2021

- g(47) = g(28) = g(16) = g(6) = 6
- g(48) = g(32) = g(6) 
- brute force: cannot beat the time complexity
- dfs?
t: how to avoid the reptitive calculation when you are calculating g(n)?
t: what is the relationship between g(n) and g(n+1)?
    - 48 = 4*7 + 4..does not seem to have an obvious relationship
t: are there repetitive calculation? seems yes 
t: how to do fast search between range? 
    g: binary search + reverse query
'''

from collections import defaultdict
from sortedcontainers import SortedList
import bisect

table = dict(zip([i for i in range(1, 10)], [i for i in range(1, 10)]))

val_key_table = defaultdict(list)
for i in range(1, 10):
    val_key_table[i].append(i)

def dfs(v):
    if v in table:
        return table[v]
    
    v_copy = v
    next_val = 1
    while v:
        cur_digit = v % 10
        if cur_digit:
            next_val *= cur_digit
        v = v // 10
    
    table[v_copy] = dfs(next_val)
    val_key_table[table[v_copy]].append(v_copy)
    return table[v_copy]

def fill_table():
    for i in range(1, 10**6+1):
       dfs(i)

def process_query():
    query = input().split()
    lower, upper, key = int(query[0]), int(query[1]), int(query[2])
    val_array = val_key_table[key]
 
    left_pos = bisect.bisect_left(val_array, lower)
    right_pos = bisect.bisect_right(val_array, upper)
    print(right_pos-left_pos)


num_query = int(input())
fill_table()
for _ in range(num_query):
    process_query()


