#include <bits/stdc++.h>
using namespace std;
vector<int> g[10];
int F[1000100];
int f(int n) {
  if (F[n] != 0) return F[n];
  int nn = n;
  int m = 1;
  while (n) {
    if (n % 10) m *= n % 10;
    n /= 10;
  }
  return F[nn] = m;
}
int G(int n) {
  if (n < 10) return n;
  return G(f(n));
}
signed main() {
  int q;
  cin >> q;
  for (int i = 1; i <= 1e6; i++) {
    g[G(i)].push_back(i);
  }
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    auto it = lower_bound(g[k].begin(), g[k].end(), r);
    if (it != g[k].end() && *it == r) *it++;
    auto it2 = lower_bound(g[k].begin(), g[k].end(), l);
    cout << it - it2 << endl;
  }
}
