#include <bits/stdc++.h>
using namespace std;
const int MAX = 2 * int(1e6);
int g[MAX + 1][20], dp[MAX + 1];
int f(int x) {
  string t = to_string(x);
  int ans = 1;
  for (auto c : t) {
    if (c == '0') continue;
    ans *= c - '0';
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  memset(g, 0, sizeof(g));
  for (int i = 0; i <= MAX; i++) {
    if (i < 10) {
      dp[i] = i;
    } else {
      dp[i] = dp[f(i)];
    }
    if (i > 0) {
      for (int j = 0; j < 10; j++) {
        g[i][j] = g[i - 1][j];
      }
    }
    g[i][dp[i]]++;
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int l, r, k;
    cin >> l >> r >> k;
    cout << g[r][k] - g[l - 1][k] << '\n';
  }
  return 0;
}
