#include <bits/stdc++.h>
using namespace std;
const long long MAX_VAL = 1000000;
long long g[1 + MAX_VAL];
long long sp[10][1 + MAX_VAL];
long long f(long long x) {
  long long prod = 1;
  while (x) {
    long long cif = x % 10;
    if (cif != 0) prod *= cif;
    x /= 10;
  }
  if (prod < 10)
    return prod;
  else if (prod < x)
    return g[prod];
  else
    return f(prod);
}
int main() {
  long long Q;
  cin >> Q;
  for (long long i = 1; i <= MAX_VAL; i++) {
    if (i < 10) {
      g[i] = i;
    } else {
      g[i] = f(i);
    }
    for (long long j = 1; j <= 9; j++) {
      sp[j][i] = sp[j][i - 1];
      if (j == g[i]) sp[j][i]++;
    }
  }
  for (long long i = 1; i <= Q; i++) {
    long long l, r, k;
    cin >> l >> r >> k;
    cout << sp[k][r] - sp[k][l - 1] << "\n";
  }
  return 0;
}
