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 = "import math\nimport sys\n\ninput = sys.stdin.readline\n\ndef main():\n\n\n\n    MAX_N = int(1e6) + 1\n\n    dp = [0 for i in range(MAX_N)]\n    vals = [[] for i in range(10)]\n\n    for i in range(10):\n        dp[i] = i\n        vals[i].append(i)\n\n\n    for i in range(10, MAX_N):\n        prod = 1\n        for j in str(i):\n            if j != '0':\n                prod *= int(j)\n\n        dp[i] = dp[prod]\n        vals[dp[prod]].append(i)\n\n    q = int(input())\n\n    for i in range(len(vals)):\n        vals[i] = sorted(vals[i])\n\n    for i in range(q):\n        l,r, k = [int(x) for x in input().split(' ')]\n        posl = -1\n        posr = -1\n        for j in range(25, -1, -1):\n            jump = 2**j\n\n            if posl + jump < len(vals[k]) and vals[k][posl+jump] < l:\n                posl += jump\n\n            if posr + jump < len(vals[k]) and vals[k][posr+jump] <= r:\n                posr += jump\n\n        print(posr - posl)\n\ndef __starting_point():\n    main()\n\n\n__starting_point()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 51391376