#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e6 + 5, MOD = 1e9 + 7;
int q, wt[N];
int lol[12][N];
int pro(int x) {
  int ret = 1;
  while (x > 0) {
    int tt = x % 10;
    if (tt) ret *= tt;
    x /= 10;
  }
  return ret;
}
void precal() {
  for (int i = 1; i < N; i++) {
    if (i < 10) {
      wt[i] = i;
    } else {
      wt[i] = wt[pro(i)];
    }
  }
  for (int i = 1; i < N; i++) {
    for (int j = 1; j < 10; j++) {
      lol[j][i] += lol[j][i - 1];
      if (wt[i] == j) lol[j][i]++;
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  precal();
  cin >> q;
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    cout << lol[k][r] - lol[k][l - 1] << endl;
  }
  return 0;
}
