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
memo = [-1 for i in range(10 ** 6 + 1)]


def f(x):
    pro = 1
    while x != 0:
        re = x % 10
        pro *= re if re != 0 else 1
        x //= 10
    return pro


def g(x):
    global memo
    if memo[x - 1] != -1:
        # print("prevented " + str(x))
        return memo[x - 1]
    else:
        if x < 10:
            return x
        else:
            memo[x - 1] = g(f(x))
            return memo[x - 1]


if __name__ == '__main__':
    pre = [[1 if i == 0 else 0] for i in range(9)]
    for i in range(2, 10 ** 6 + 1):
        val = g(i)
        for j in range(9):
            if j == val - 1:
                pre[j].append(pre[j][-1] + 1)
            else:
                pre[j].append(pre[j][-1])
    q = int(input().strip())
    for _ in range(q):
        l, r, k = [int(__) for __ in input().strip().split()]
        l -= 1
        r -= 1
        if l == 0:
            print(pre[k - 1][r])
        else:
            print(pre[k - 1][r] - pre[k - 1][l - 1])
    # print(memo)
