#include <bits/stdc++.h>   using namespace std;   long long ans[1000005], anss[1000005][10];   int make(int n) {     long long g = 1;     if (n % 10 != 0) g = g * (n % 10);     n = n / 10;     while (n > 0) {       if (n % 10 != 0) g = g * (n % 10);       n = n / 10;     }     return g;   }   long long bit[1000005][11];   void update(int idx, int val) {     while (idx <= 1000000) {       bit[idx][val]++;       idx += idx & (-idx);     }   }   long long query(int idx, int val) {     long long sum = 0;     while (idx > 0) {       sum += bit[idx][val];       idx -= idx & (-idx);     }     return sum;   }   int main() {     long long int i;     ans[1] = 1;     ans[0] = 0;     for (i = 2; i <= 9; i++) {       ans[i] = i;     }     int k;     for (int i = 10; i <= 1000000; i++) {       k = i;       while (make(k) >= 10) {         k = make(k);       }       k = make(k);       ans[i] = k;     }     for (i = 1; i <= 1000000; i++) {       update(i, ans[i]);     }     int q;     cin >> q;     while (q--) {       int l, r, k;       cin >> l >> r >> k;       cout << query(r, k) - query(l - 1, k) << endl;     }   }   