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 math
from bisect import bisect_left, bisect_right

MOD = int(1e9+7)
MAX = int(1e6+10)

def redux(i):
    mt = 1;
    while(i > 0):
        d = i % 10
        if(d >0): mt *= d
        i //= 10
    
    return mt

idxs = [[] for _ in range(10)]
pre = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(1, 10):
    idxs[i].append(i)

for i in range(10, MAX):
    val = pre[redux(i)]
    idxs[val].append(i)
    pre.append(val)

def lower_bound(i, x):
    l = 0
    r = len(idxs[x]) - 1
    ans = len(idxs[x]);
    while(l <= r):
        m = (l + r) // 2

        if(idxs[x][m] >= i):
            ans = m
            r = m-1
        else: l = m + 1
    
    return ans

def upper_bound(i, x):
    l = 0
    r = len(idxs[x]) - 1
    ans = len(idxs[x]);
    while(l <= r):
        m = (l + r) // 2

        if(idxs[x][m] > i):
            ans = m
            r = m-1
        else: l = m + 1
    
    return ans

def solve_test_case():
     l, r, x = map(int, input().split())
     count = upper_bound(r, x) - lower_bound(l, x)
     print(count)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve_test_case()

	    	 		   		  		  		  		 				