#include <bits/stdc++.h>
using namespace std;
int partsum[10][1000005];
int pd(int n) {
  int ans = 1;
  while (n != 0) {
    ans *= (n % 10 == 0) ? 1 : n % 10;
    n /= 10;
  }
  return ans < 10 ? ans : pd(ans);
}
int main() {
  for (int i = 1; i <= 9; i++) {
    partsum[i][i] = 1;
    for (int j = i; j <= 9; j++) partsum[i][j] = 1;
  }
  for (int i = 10; i <= 1000000; i++) {
    int multi = pd(i);
    for (int j = 1; j <= 9; j++) {
      partsum[j][i] = partsum[j][i - 1] + (j == multi);
    }
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    printf("%d\n", partsum[k][r] - partsum[k][l - 1]);
  }
  return 0;
}
