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
p = [0] * 6
s = [0] * 6
ans = [0] * 1000000
for i in range(10):
    ans[i] = i
for a in range(10):
    s[0] = a
    p[0] = a if a != 0 else 1
    for b in range(10):
        s[1] = s[0]*10 + b
        p[1] = p[0] * b if b != 0 else p[0]
        for c in range(10):
            s[2] = s[1]*10 + c
            p[2] = p[1]*c if c != 0 else p[1]
            for d in range(10):
                s[3] = s[2]*10 + d
                p[3] = p[2]*d if d != 0 else p[2]
                for e in range(10):
                    s[4] = s[3]*10 + e
                    p[4] = p[3]*e if e != 0 else p[3]
                    for f in range(10):
                        s[5] = s[4]*10 + f
                        p[5] = p[4]*f if f != 0 else p[4]
                        if p[5] < 10:
                            ans[s[5]] = p[5]
                        else:
                            ans[s[5]] = ans[p[5]]
Q = int(input())
for i in range(Q):
    l, r, k = list(map(int, input().split()))
    cnt = 0
    for j in range(l, r+1):
        if ans[j] == k:
            cnt += 1
    print(cnt)
                        
                
