Let us define two functions f and g on positive integer numbers.  $f(n) = \text{product of non-zero digits of} n$

$g(n) = \left\{\begin{array}{ll}{n} & {\text{if} n < 10} \\{g(f(n))} & {\text{otherwise}} \end{array} \right.$ 

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. 


-----Input-----

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 10^5) representing the number of queries. 

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 10^6, 1 ≤ k ≤ 9).


-----Output-----

For each query, print a single line containing the answer for that query.


-----Examples-----
Input
4
22 73 9
45 64 6
47 55 7
2 62 4

Output
1
4
0
8

Input
4
82 94 6
56 67 4
28 59 9
39 74 4

Output
3
1
1
5



-----Note-----

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

Source: codeforces | Difficulty: EASY
Tags: Sorting

Data structures

Graph traversal


Solutions:
import math
import sys
input = sys.stdin.readline

def main():
	MAX_N = int(1000000.0) + 1
	dp = [0 for i in range(MAX_N)]
	vals = [[] for i in range(10)]
	for i in range(10):
		dp[i] = i
		vals[i].append(i)
	for i in range(10, MAX_N):
		prod = 1
		for j in str(i):
			if j != '0':
				prod *= int(j)
		dp[i] = dp[prod]
		vals[dp[prod]].append(i)
	q = int(input())
	for i in range(len(vals)):
		vals[i] = sorted(vals[i])
	for i in range(q):
		(l, r, k) = [int(x) for x in input().split(' ')]
		posl = -1
		posr = -1
		for j in range(25, -1, -1):
			jump = 2 ** j
			if posl + jump < len(vals[k]) and vals[k][posl + jump] < l:
				posl += jump
			if posr + jump < len(vals[k]) and vals[k][posr + jump] <= r:
				posr += jump
		print(posr - posl)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
import sys

def f(n):
	out = 1
	while n > 0:
		digit = n % 10
		if digit != 0:
			out *= digit
		n = n // 10
	return out
memorization = defaultdict(int)

def g(n):
	if n < 10:
		return n
	f_n = f(n)
	if f_n in memorization:
		return memorization[f_n]
	else:
		ans = g(f_n)
		memorization[f_n] = ans
		return ans

def s(L, l, r, k):
	if l > r:
		return l
	m = (l + r) // 2
	if L[m] == k:
		return m
	if L[m] > k:
		return s(L, l, m - 1, k)
	else:
		return s(L, m + 1, r, k)
ans = {i: [1000001] for i in range(1, 10)}
for i in range(1, 1000001):
	g_i = g(i)
	if g_i != 0:
		ans[g_i].append(i)
for i in ans:
	ans[i].sort()
input = sys.stdin.readline
n = int(input())
for i in range(n):
	(l, r, k) = [int(i) for i in input().split()]
	(l_idx, r_idx) = (s(ans[k], 0, len(ans[k]) - 1, l), s(ans[k], 0, len(ans[k]) - 1, r))
	if ans[k][l_idx] != l and ans[k][l_idx] < l and (ans[k][l_idx + 1] > l):
		l_idx += 1
	if ans[k][r_idx] != r and (not (ans[k][r_idx] < r and ans[k][r_idx + 1] > r)):
		r_idx -= 1
	print(r_idx - l_idx + 1)


import bisect as b
from sys import stdin
inp = stdin.readline
pre_calc = x = [[] for i in range(10)]

def get_g(num):
	while num > 9:
		new_num = 1
		while num:
			digit = num % 10
			if digit:
				new_num *= digit
			num //= 10
		num = new_num
	return num
for i in range(1, 10 ** 6 + 5):
	pre_calc[get_g(i)].append(i)
q = int(inp())
while q:
	q -= 1
	(l, r, x) = list(map(int, inp().split()))
	index_l = b.bisect_left(pre_calc[x], l)
	if index_l < len(pre_calc[x]) and pre_calc[x][index_l] >= l:
		index_l -= 1
	index_r = b.bisect_left(pre_calc[x], r)
	if index_r < len(pre_calc[x]) and pre_calc[x][index_r] <= r:
		index_r += 1
	print(max(index_r - index_l - 1, 0))