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 functools import *
from time import time


max = int(10e6 + 42)


def measure_time(fun):
    def wrapper(*args, **kwargs):
        begin = time()
        rv = fun(*args, **kwargs)
        end = time()
        print(end - begin)
        return rv
    return wrapper


def our_cache(func):
    memo = [-1]*(max+1)

    @wraps(func)
    def wrapper(arg):
        if memo[arg] == -1:
            memo[arg] = func(arg)
        return memo[arg]
    return wrapper


@measure_time
def solve(l, r):
    for i in range(l, r+1):
        g(i)


@measure_time
def test():
    for i in range(max):
        "".join("")


def main():
    test()
    # for i in range(1, max+1):
    #     if i % 100000 == 0:
    #         solve(i, i + 100000)
    # results = list(solve(max))
    # for i in range(1, 10):
    #     print(i, ":", len(list(filter((lambda x: x == i), results[:100000]))))
    # for i in list(filter((lambda x: x[1] == 1), enumerate(results[:1000]))):
    #     print(i[0])
    # # q = int(input())
    # queries = ((1, max, 5),)*2
    # # queries = []
    # # for _ in range(q):
    # #     queries.append([int(x) for x in input().split()])
    # for l, r, k in queries:
    #     print(results[k-1][r] - results[k-1][l-1])


def f(n):
    x = 1
    while n >= 10:
        a = n % 10
        if a != 0:
            x *= a
        n //= 10
    return x*n


# def f(n):
#     return reduce((lambda x,y: int(x) if int(y) == 0 else int(x)*int(y)), str(n))


@our_cache
def g(n):
    if n < 10:
        return n
    return g(f(n))


if __name__ == "__main__":
    main()