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 math import * 
from heapq import heappop, heappush
MOD = 10**9 + 7
#input=sys.stdin.readline

    #map(int, input().split())
    #list(map(int, input().split()))
class Solution():
    pass
def solution():
    q = int(input()) 
    querys = []
    o = 10
    for _ in range(q):
        l,r,q = map(int, input().split())
        querys.append((l,r,q))
        o = max(o, r)

    dp = [None]*(o + 1)
    for i in range(0, 10):
        dp[i] = i

    for i in range(10, len(dp)):
        dp[i] = dp[prod([int(val) for val in str(i) if val != '0' ])]
    
    running_count = [0]*10
    count_arr = []
    for i in range(len(dp)):
        running_count[dp[i]] += 1
        count_arr.append(running_count.copy())
    
    for l,r,k in querys:
        print(count_arr[r][k] - count_arr[l-1][k])

 
        

def main():
    #test()
    t = 1
    #t = int(input())
    for _ in range(t):
        solution() 

#import sys
#import threading
#sys.setrecursionlimit(10**6)
#threading.stack_size(1 << 27)
#thread = threading.Thread(target=main)
#thread.start(); thread.join()
main()
