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
import sys

raw_input = lambda: sys.stdin.readline().rstrip()

r_s = lambda: raw_input().strip()                   #read str
r_ss = lambda: raw_input().split()          #read stringss
r_i = lambda: int(raw_input())              #read int
r_is = lambda: map(int, raw_input().split())#read ints
r_f = lambda: float(raw_input())            #read float
r_fs = lambda: map(Decimal, raw_input().split()) #read floats

# For effieciently taking lots of queries with each query in a separate line
# having integer values separated by space. A 2d list is made with each row
# corresponding to line. Each row is a list with all the values.
# Use this for fast I/O by taking all input in one go.
r_qs = lambda: map(lambda s:map(int, s.split(' ')), sys.stdin.readlines())

'''-------------------------------------------------------------------'''

def main():
    q = r_i()
    arr = [-1 for i in range(10**6+2)]

    def f(x):
        prod  = 1
        while x!=0:
            if x%10!=0:
                prod*=(x%10)
            x/=10
        return prod

    def g(x):
        if arr[x]!=-1:
            return arr[x]
        if x<10:
            return x
        return g(f(x))

    for i in range(1, 10**6+1):
        arr[i] = g(i)

    prefsum = [[0 for i in range(10**6+2)] for j in range(10)]
    for i in range(1, 10):
        cnt = 0
        for j in range(1, 10**6+1):
            if arr[j]==i:
                cnt+=1
            prefsum[i-1][j] = cnt
    ans = []
    queries = r_qs()
    for i in xrange(q):
        l,r,k = queries[i][0], queries[i][1], queries[i][2]
        ans.append(str(prefsum[k-1][r] - prefsum[k-1][l-1]))
    print '\n'.join(ans)

if __name__ == '__main__':
    local = True
    # local = False
    if local:
        try:
            sys.stdin = open('input.txt')
            print 'Running at local.'
            for i in range(r_i()):
                main()
        except IOError:
            main()
    else:
        main()