#include <bits/stdc++.h>
int i, g[1000000 + 1], j, Sg[1000000 + 1][10], n, fn, _, Q, l, r, k;
int main() {
  for (i = 1; i <= 9; ++i) {
    g[i] = i;
    for (j = 1; j <= i; ++j) Sg[i][j] = 1;
  }
  for (i = 10; i <= 1000000; ++i) {
    n = i, fn = 1;
    do
      if (_ = n % 10) fn *= _;
    while (n /= 10);
    g[i] = g[fn];
    for (j = 1; j <= 9; ++j) Sg[i][j] = Sg[i - 1][j];
    ++Sg[i][g[i]];
  }
  std::cin >> Q;
  while (Q--) {
    std::cin >> l >> r >> k;
    std::cout << Sg[r][k] - Sg[l - 1][k] << std::endl;
  }
}
