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

Difficulty: competition

Starter code:

Solutions:
import math
import sys

input = sys.stdin.readline

def main():



    MAX_N = int(1e6) + 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()

import math
import sys

input = sys.stdin.readline

def main():



    MAX_N = int(1e6) + 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): # O(digits)
    out = 1
    while(n > 0):
        digit = n % 10
        if digit != 0:
            out *= digit
        n = n//10
    return out

memorization = defaultdict(int) # For much faster calculation g(n)
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): # O(n) because 9*9*9*9*9*9 = 531441 -> Maxnimum each number between [1,531441] will calculated only once
    g_i = g(i)             # due to memorization
    if g_i != 0:ans[g_i].append(i)    
for i in ans: # O( nlog(n) )
    ans[i].sort()

input = sys.stdin.readline
n = int(input())
for i in range(n): # O( Qlog(n) )
    l,r,k = [int(i) for i in input().split()] #O (logn) for each Q
    l_idx,r_idx = s(ans[k],0,len(ans[k])-1,l) , s(ans[k],0,len(ans[k])-1,r)
    #FIX l_idx to Upper_bound
    if ans[k][l_idx] != l and ans[k][l_idx] < l and ans[k][l_idx+1] > l : l_idx += 1
    #FIX r_idx to Lower_bound
    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)
    


# -*- coding: utf-8 -*-

# Baqir Khan
# Software Engineer (Backend)

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))