#include <bits/stdc++.h>
using namespace std;
int sum[1000006][10] = {0};
int f(int x) {
  if (x < 10) return x;
  int ans = 1;
  while (x) {
    if (x % 10) ans *= x % 10;
    x /= 10;
  }
  return f(ans);
}
int main() {
  for (int i = 1; i <= 1000000; ++i) ++sum[i][f(i)];
  for (int i = 1; i <= 1000000; ++i)
    for (int j = 1; j <= 10; ++j) sum[i][j] += sum[i - 1][j];
  int T, l, r, k;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", sum[r][k] - sum[l - 1][k]);
  }
  return 0;
}
