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 bisect
q = int(input())
l = []
r = []
k = []
for i in range(q):
	a, b, c = list(map(int,input().strip().split()))
	l.append(a)
	r.append(b)
	k.append(c)
buckets = {k: [] for k in range(10)}
memo = dict()

def compute(n):
	if n == 0:
		return 1
	curr = n % 10
	if curr == 0:
		curr = 1
	return curr * compute(n // 10)

def solve(n, seq):
	if n >= 10:
		if n not in memo:
			res = compute(n)
			seq.append(res)
			return solve(res, seq)
		else:
			for i in range(len(seq)):
				memo[seq[i]] = memo[n]
			return memo[n]
	else:
		for i in range(len(seq)):
			memo[seq[i]] = n
		return n

for i in range(min(l),max(r)+1):
	curr = solve(i,[] )
	(buckets[curr]).append(i)

for i in range(q):
	lindex = bisect.bisect_left(buckets[k[i]],l[i])
	rindex = bisect.bisect_right(buckets[k[i]],r[i])
	print(rindex - lindex)

