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
from collections import defaultdict
def f(n): # O(digits)
    out = 1
    while(n > 0):
        digit = n % 10
        if digit != 0:
            out *= digit
        n = n//10
    return out

memorization = defaultdict(int) # For much faster calculation g(n)
def g(n):
    if n < 10:return n
    f_n = f(n)
    if f_n in memorization:
        return memorization[f_n]
    else:
        ans = g(f_n)
        memorization[f_n] = ans
        return ans

def s(L,l,r,k):
    if l > r:return l
    m = (l+r)//2
    if L[m] == k:return m
    if L[m] > k:return s(L,l,m-1,k)
    else:return s(L,m+1,r,k)

ans = {i : [] for i in range(0,10)}

for i in range(1,1000001): # O(n) because 9*9*9*9*9*9 = 531441 -> Maxnimum each number between [1,531441] will calculated only once
    ans[g(i)].append(i)    # due to memorization
for i in ans: # O( nlog(n) )
    ans[i].sort()

n = int(input())
for i in range(n): # O( Qlog(n) )
    l,r,k = [int(i) for i in input().split()] #O (logn) for each Q
    l_idx,r_idx = s(ans[k],0,len(ans[k])-1,l) , s(ans[k],0,len(ans[k])-1,r)
    #FIX l_idx to Upper_bound
    if ans[k][l_idx] != l and ans[k][l_idx] < l and ans[k][l_idx+1] > l : l_idx += 1
    #FIX r_idx to Lower_bound
    if ans[k][r_idx] != r and not (ans[k][r_idx] < r and ans[k][r_idx+1] > r) : r_idx -= 1
    print(r_idx - l_idx + 1)
    
