#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e6 + 1;
 
int dp[N][10];
 
 
ll f(ll x) {
ll ret = 1;
while (x) {
    ret *= max(1ll, x % 10);
    x /= 10;
}
return ret;
}
 
ll g(ll x) {
    return (x < 10 ? x : g(f(x)));
}
 
int main() {
 
for (int i = 1; i < N; i++) {
dp[i][g(i)]++;
for (int j = 1; j <= 9; j++)
    dp[i][j] += dp[i - 1][j];
}
 
int q; cin >> q;
 
while (q--) {
    int l, r, k; cin >> l >> r >> k;
    cout << dp[r][k] - dp[l - 1][k] << endl;
}
 
return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBsbCA9IGxvbmcgbG9uZzsKY29uc3QgaW50IE4gPSAxZTYgKyAxOwoKaW50IGRwW05dWzEwXTsKCgpsbCBmKGxsIHgpIHsKbGwgcmV0ID0gMTsKd2hpbGUgKHgpIHsKICAgIHJldCAqPSBtYXgoMWxsLCB4ICUgMTApOwogICAgeCAvPSAxMDsKfQpyZXR1cm4gcmV0Owp9CgpsbCBnKGxsIHgpIHsKICAgIHJldHVybiAoeCA8IDEwID8geCA6IGcoZih4KSkpOwp9CgppbnQgbWFpbigpIHsKCmZvciAoaW50IGkgPSAxOyBpIDwgTjsgaSsrKSB7CmRwW2ldW2coaSldKys7CmZvciAoaW50IGogPSAxOyBqIDw9IDk7IGorKykKICAgIGRwW2ldW2pdICs9IGRwW2kgLSAxXVtqXTsKfQoKaW50IHE7IGNpbiA+PiBxOwoKd2hpbGUgKHEtLSkgewogICAgaW50IGwsIHIsIGs7IGNpbiA+PiBsID4+IHIgPj4gazsKICAgIGNvdXQgPDwgZHBbcl1ba10gLSBkcFtsIC0gMV1ba10gPDwgZW5kbDsKfQoKcmV0dXJuIDA7Cn0=

NAo4MiA5NCA2CjU2IDY3IDQKMjggNTkgOQozOSA3NCA0Cgo=

4
82 94 6
56 67 4
28 59 9
39 74 4