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

Firstly, for all n >= 10, f(n) < n. 

Why is this important ?

So, g(n) = g(f(n)) ... We can calculate this bottom-up.

--------------------------------------------------

I didn't prove it during the contest. The editorial had a nice proof.

Let N = n1 n2 n3 ... nk

So, product is at most = n1 x n2 x ... x nk

Now, N = nk + 10n(k - 1) + ... + 10^(k - 1)n1

Now, each nk is at most 9. 

Product of digits <= 9^(k -1)n1 < 10^(k - 1)n1 < N

-------------------------------------------------------

The key to note is that in the query [L, R, k], k is small < 10. 

So, we precompute g(i, k) for all i <= 10^6 and all k < 10. This allows us to answer the query in O(1) time. 

Here is the main idea ... Since f(n) < n ... Whenever we are at i, we have all values of g(x), where x < i. 

We simply find g(f(i))

Now, while storing the answer ..., Here's what we do -

Let answer(i, k) be the number of numbers in the range [1, i] for which g(i) = k. 

If we know this, how can we calculate g(i + 1, k) ? 

There are two possibilities - Either g(i + 1) = k, or g(i + 1) =/= k

If g(i + 1) =/= k, then Answer(i + 1, k) = Answer(i, k)

If g(i + 1) = k, then Answer(i + 1, k)  = Answer(i, k) + 1

Do this for all k from 1 to 9.

This idea of precomputing the answers using a 2D array, I had come across in some SPOJ question a long time back. 

----------------------------------------------------------------

const int LIMIT = 1e6 + 5;
int answer[LIMIT][10];

int non_zero_digit_product(int n)
{
    int product = 1;

    while(n)
    {
        product *= (n%10 != 0 ? n%10 : 1);
        n /= 10;
    }

    return product;
}

void precompute()
{
    vector <int> g(LIMIT, 0);
    for(int i = 1; i < LIMIT; i++)
        g[i] = (i < 10 ? i : g[non_zero_digit_product(i)]);

    for(int i = 1; i < LIMIT; i++)
        answer[i][0] = 0;

    for(int i = 1; i < LIMIT; i++)
    {
        for(int digit = 1; digit < 10; digit++)
        {
            answer[i][digit] = answer[i - 1][digit];
        }

        if(g[i] < 10)
            answer[i][g[i]]++;
    }
}

int main()
{
    precompute();

    int no_of_queries;
    scanf("%d", &no_of_queries);

    while(no_of_queries--)
    {
        int left, right, k;
        scanf("%d %d %d", &left, &right, &k);

        printf("%d\n", answer[right][k] - answer[left - 1][k]);
    }

    return 0;
}
 	   			  	 	 	  		  		 	 		  	