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
def recurs(n,an,arr):
    while len(n)!=1:
        # print("n",n)
        if arr[int(n)]:
            arr[an]=arr[int(n)]
            return
        prod=1
        for i in n:
            if int(i):
                prod *= int(i)
        n=str(prod)
    arr[an]=int(n)
def findSq():
    arr=[0 for i in range(1,1000010)]
    for i in range(1,1000001):
        # print(i,end=" ")
        recurs(str(i),i,arr)
    return arr
arr=findSq()
a1=[0 for i in range(0,1000010)]
a2=[0 for i in range(0,1000010)]
a3=[0 for i in range(0,1000010)]
a4=[0 for i in range(0,1000010)]
a5=[0 for i in range(0,1000010)]
a6=[0 for i in range(0,1000010)]
a7=[0 for i in range(0,1000010)]
a8=[0 for i in range(0,1000010)]
a9=[0 for i in range(0,1000010)]
for index in range(1,len(arr)):
    if arr[index]==9:
        a9[index]=1
    if arr[index] == 8:
        a8[index] = 1
    if arr[index] == 7:
        a7[index] = 1
    if arr[index] == 6:
        a6[index] = 1
    if arr[index] == 5:
        a5[index] = 1
    if arr[index] == 4:
        a4[index] = 1
    if arr[index] == 3:
        a3[index] = 1
    if arr[index] == 2:
        a2[index] = 1
    if arr[index] == 1:
        a1[index] = 1
for i in range(1,len(a1)):
    a1[i]+=a1[i-1]
    a2[i] += a2[i - 1]
    a3[i] += a3[i - 1]
    a4[i] += a4[i - 1]
    a5[i] += a5[i - 1]
    a6[i] += a6[i - 1]
    a7[i] += a7[i - 1]
    a8[i] += a8[i - 1]
    a9[i] += a9[i - 1]
t=int(input())
for b in range(t):
    l,r,k=[int(i) for i in input().split(" ")]
    if k==9:
        print(a9[r]-a9[l-1])
    if k == 8:
        print(a8[r] - a8[l - 1])
    if k == 7:
        print(a7[r] - a7[l - 1])
    if k == 6:
        print(a6[r] - a6[l - 1])
    if k == 5:
        print(a5[r] - a5[l - 1])
    if k == 4:
        print(a4[r] - a4[l - 1])
    if k == 3:
        print(a3[r] - a3[l - 1])
    if k == 2:
        print(a2[r] - a2[l - 1])
    if k == 1:
        print(a1[r] - a1[l - 1])

