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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from collections import defaultdict\nimport sys\ndef f(n): # O(digits)\n    out = 1\n    while(n > 0):\n        digit = n % 10\n        if digit != 0:\n            out *= digit\n        n = n//10\n    return out\n\nmemorization = defaultdict(int) # For much faster calculation g(n)\ndef g(n):\n    if n < 10:return n\n    f_n = f(n)\n    if f_n in memorization:\n        return memorization[f_n]\n    else:\n        ans = g(f_n)\n        memorization[f_n] = ans\n        return ans\n\ndef s(L,l,r,k):\n    if l > r:return l\n    m = (l+r)//2\n    if L[m] == k:return m\n    if L[m] > k:return s(L,l,m-1,k)\n    else:return s(L,m+1,r,k)\n\nans = {i : [1000001] for i in range(1,10)}\n\nfor 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\n    g_i = g(i)             # due to memorization\n    if g_i != 0:ans[g_i].append(i)    \nfor i in ans: # O( nlog(n) )\n    ans[i].sort()\n\ninput = sys.stdin.readline\nn = int(input())\nfor i in range(n): # O( Qlog(n) )\n    l,r,k = [int(i) for i in input().split()] #O (logn) for each Q\n    l_idx,r_idx = s(ans[k],0,len(ans[k])-1,l) , s(ans[k],0,len(ans[k])-1,r)\n    #FIX l_idx to Upper_bound\n    if ans[k][l_idx] != l and ans[k][l_idx] < l and ans[k][l_idx+1] > l : l_idx += 1\n    #FIX r_idx to Lower_bound\n    if ans[k][r_idx] != r and not (ans[k][r_idx] < r and ans[k][r_idx+1] > r) : r_idx -= 1\n    print(r_idx - l_idx + 1)\n    \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 40581127