#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000001;
int F[MAX], G[MAX], T[10][2 * MAX + 1];
void calculate_F() {
  for (int i = 1; i < 10; i++) F[i] = i;
  for (int i = 10; i < MAX; i++) {
    int last_digit = i % 10;
    F[i] = F[i / 10];
    if (last_digit != 0) F[i] *= last_digit;
  }
}
void calculate_G() {
  for (int i = 1; i < 10; i++) G[i] = i;
  for (int i = 10; i < MAX; i++) G[i] = G[F[i]];
}
void insert(int k, int x) {
  int v = MAX + x;
  T[k][v]++;
  while (v != 1) {
    v /= 2;
    T[k][v]++;
  }
}
int query(int k, int a, int b) {
  int v_a = MAX + a;
  int v_b = MAX + b;
  int result = T[k][v_a];
  if (v_a != v_b) result += T[k][v_b];
  while (v_a / 2 != v_b / 2) {
    if (v_a % 2 == 0) result += T[k][v_a + 1];
    if (v_b % 2 == 1) result += T[k][v_b - 1];
    v_a /= 2;
    v_b /= 2;
  }
  return result;
}
void create_segment_trees() {
  for (int i = 1; i < MAX; i++) insert(G[i], i);
}
int main() {
  int Q;
  calculate_F();
  calculate_G();
  create_segment_trees();
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    cout << query(k, l, r) << endl;
  }
  return 0;
}
