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
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
typedef pair<double,double>         pdd;
typedef pair<ld,ld>                 pld;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define endt                        '\t'
#define ends                        ' '
#define error(x)                    cerr << #x << " = " << x << endl

int calc(int n)
{
    int mul=1;
    while(n>=10)
    {
        while(n!=0)
        {
            if(n%10!=0)
            {
                mul*=(n%10);
            }
            n/=10;
        }
        n=mul;
        mul=1;
    }
    return n;
}

int main()
{
    vector<int> a(1000*1000+1);
    for(int i=1;i<1000*1000;i++)
    {
         a[i]=calc(i);
    }
    int n;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        int l,r,k , ans=0;
        cin >> l >> r >> k;

        for(int j=l;j<=r;j++)
        {
            if(a[j]==k)
            {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
