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
n = int(input());
A = [];
L = [];
R = [];
K = [];
for q in range(n):
    l, r, k = map(int, input().split());
    L.append(l);
    R.append(r);
    K.append(k);
B = [];
for q in range(max(R) + 1):
    B.append(0);
for e in range(max(R) + 1):
    q = e;
    while q > 9:
        qs = str(q);
        q = 1;
        for w in range(len(qs)):
            #if qs == "71":
                #print(q);
            if qs[w] != "0":
                q = q * int(qs[w]);
    B[e] = q;
cnt = 0;
RE = [];
for q in range(9):
    D = [];
    for w in range(max(R) + 1):
        D.append(0);
    RE.append(D);
for q in range(1, max(R) + 1):
    for w in range(9):
        RE[w][q] = (RE[w][q - 1]);
        #print(RE[w][q - 1]);
    RE[B[q] - 1][q] += 1;
for q in range(n):
    k = K[q];
    l = L[q];
    r = R[q];
    #print(RE[k - 1][r], RE[k - 1][l]);
    print(RE[k - 1][r] - RE[k - 1][l - 1]);
#print(*RE[8]);
#print(*RE);
#print(*B);