#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
#define pb push_back

int maxn=1000003;
vector<int> ans(maxn);

int main(){
	forn(i, 10)ans[i]=i;
	forsn(i, 10, maxn){
		int pro=1;
		int nc=i;
		while(nc){
			int l=nc%10;
			if(l)pro*=l;
			nc/=10;
		}
                // calculo g(i) dinamicamente usando que el producto de los digitos siempre es menor que el numero
		ans[i]=ans[pro];
	}
	vector< vector<int> > cant;
	vector<int> dec(10, 0);
	cant.pb(dec); // para que si l=1, cant[l-1][k]=cant[0][k] de 0 para cualquier k
	forsn(i, 1, maxn){
		dec.clear();
		forn(j, 10){
			dec.pb(cant[i-1][j]);
		}
		dec[ans[i]]++;
		cant.pb(dec);
	}
	int n;
	cin>>n;
	while(n--){
		int l, r, k;
		cin>>l>>r>>k;
		cout<<cant[r][k]-cant[l-1][k]<<"\n";
	}
}