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
# MAXSIZE  = 2**20
# from functools import lru_cache
#
# @lru_cache(maxsize=MAXSIZE)
# def f(n):
#     cel, rem = n // 10, n % 10
#
#     if rem > 0:
#         prodct = rem
#     else:
#         prodct = 1
#
#     while cel > 0:
#         rem = cel % 10
#         cel = cel // 10
#         if rem > 1:
#             prodct *= rem
#
#     return prodct
#
# @lru_cache(maxsize=MAXSIZE)
# def g(n):
#     if n<10:
#         return n
#     else:
#         return g(f(n))
#
def check(new_n):
    res = new_n
    for i in [2,3,5,7]:
        while res %i == 0:
            res //= i
    return res <2

f = [1]*1000001
g = [1]*1000001

for cnt in range (1, 10):
    f[cnt] = cnt
    g[cnt] = cnt

for cnt in range (10, 1000001):
    rem = cnt % 10

    if rem >1:
        f[cnt] = f[cnt//10] * rem
    else:
        f[cnt] = f[cnt//10]

    g[cnt] = g[f[cnt]]




Q = int (input())
for cnt in range(Q):
    l,r,k = list(map (int, input().split()))
    res = 0
    if check(k):
        l  = max(l,k)
        for cur_n in range(l, r+1):
            if g[cur_n] == k:
               res += 1
    print (res)

