DIGITX

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define task "DIGITX"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 1;
vector<int> s[10];
int dp[N], l, r, k, q;

int Convert(int v)
{
    int ans = 1;
    while (v)
    {
        if (v % 10 != 0)
            ans *= v % 10;
        v /= 10;
    }
    return ans;
}

void Prepare()
{
    for (int i = 1; i < 10; ++i)
        dp[i] = i,
        s[i].push_back(i);
    for (int i = 10; i < N; ++i)
        dp[i] = dp[Convert(i)],
        s[dp[i]].push_back(i);
}

void Read()
{
    cin >> l >> r >> k;
}

void Solve()
{
    cout << upper_bound(s[k].begin(), s[k].end(), r) - lower_bound(s[k].begin(), s[k].end(), l) << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Prepare();
    for (cin >> q; q--;)
        Read(),
            Solve();
}