很显然，这道题需要用数位dp，按照套路转化成求 $[1..X]$ 中重要度为 $K$ 的编号和。

在不考虑空间的情况下，我们定义 $f(i,j,0/1,0/1)$ 表示现在正在考虑从高到低的第 $i$ 位，当前位和更低位上的数码乘积需要等于 $j$（即更高位的乘积为 $\frac K j$），目前贴/没贴上界，目前在/不在前导零阶段，重要度为 $K$ 的编号和。答案就是 $f(1,K,1,1)$ 。

因为求的是编号和，所以还需要记一个 $g(i,j,0/1,0/1)$ 表示上述情况下的重要度为 $k$ 的人数。

如果这道题的 $K$ 很小，那么这道题就是数位dp模板了，但是这道题的 $K$ 显然是可以非常大的，所以按常规方法开数组肯定开不下。但是，不难发现有些状态是肯定不会出现的，即状态中的 $j$ 不是若干数码的乘积，于是考虑离散化。

分析一下某个人重要度 $K$ 的组成，发现一个合法的 $j$ 一定可以表示成这样（此处为了方便假设 $0^0=1$）：

$$j=0^{a_0}\times1^{a_1}\times2^{a_2}\times...\times9^{a_9}$$

其中 $a_i$ 表示 $i$ 这个数码在 $j$ 中出现了多少次。

通过这个发现，就可以暴力枚举指数 $a_i$ ，得到所有可能出现的乘积，这样就成功完成了离散化。可是这时又出现了一个问题：离散化后的数没法正常进行运算！

所以，我们的处理工作还未结束。定义 $to_{i,j}$ 表示 $i$ 这个离散化后的数的原值除以数码 $j(1\le j\le9)$ 得到的结果离散化后的值。因为 $i$ 能表示成若干个数码之积，所以 $to_{i,j}$ 也可以，这就保证了 $to_{i,j}$ 也在离散化后的那些数之中。

你可能会问：$j$ 不能等于 $0$ ，这样会少考虑一些情况啊！

不用担心，$0$ 的问题稍后解决。

现在我们先考虑 $K\not=0$ 的情况下 $f$ 的状态转移方程，这时肯定不能有任何数码为 $0$ ，所以设 $p$ 为当前位的上界， $x=p\land[k=up],y=q\land[k=0]$：

$$g(i,j,p,q)=\sum_{k=1}^{up}g(i+1,to_{j,k},x,y)$$ $$f(i,j,p,q)=\sum_{k=1}^{up}g(i+1,to_{j,k},x,y)\times k\times10^{19-i}+f(i+1,to_{j,k},x,y)$$

对于第二个式子中 $10$ 的幂次，因为我计算的是从高到低第 $i$ 位，所以应该用总位数减去 $i$ 作为指数。在这道题中我的总位数为 $19$ 。

这样，对于 $K\not=0$ 的情况就讨论完了，下面看应该如何处理 $0$ 。

如果一个数中有任意一个数码是 $0$ ，那么这个数所有位的乘积一定是 $0$ 。那么 $K=0$ 的情况就可以简化为求含有至少一个 $0$ 的数的编号和。

进一步可以用容斥简化为更好求的：不含 $0$ 的数的编号和。

这样就按照类似求 $f$ 和 $g$ 的套路再做一遍，便可求出这种情况的答案。

实现起来很简单，记忆化深搜即可。

代码如下，求个赞支持一下QWQ

#include <bits/stdc++.h>
#define int long long
#define g(x,y,z) (z?x:to[x][y])
using namespace std;

const int N=5e6+3,upK=1e18,Mod=20120427;
struct node{
	int num,sum;
}f[25][60005],dp[25];
int T,A,B,K,tp=1,tot,nw,a[25],lsh[N],pow10[25],to[60005][10];
bool vis[25][60005],viss[25];
unordered_map<int,int>mp;

void pre(int i,int prod,int j){
	if(j<0)return;
	if(i>9){lsh[++tp]=prod;return;}
	int cnt=prod;
	for(int k=0;k<=j&&cnt<=upK;k++,cnt*=i)pre(i+1,cnt,j-k);
}

node F(int i,int j,bool up,bool pre0){
	if(j==0)return {0,0};
	if(i>19)return (node){j==2,0};
	if(!up&&!pre0&&vis[i][j])return f[i][j];
	int r=up?a[i]:9;
	node res={0,0};
	for(int k=0;k<=r;k++){
		node add=F(i+1,g(j,k,pre0&(k==0)),up&(k==r),pre0&(k==0));
		(res.num+=add.num)%=Mod;
		(res.sum+=(add.num*pow10[19-i]%Mod*k%Mod+add.sum)%Mod)%=Mod;
	}
	if(!up&&!pre0)vis[i][j]=1,f[i][j]=res;
	return res;
}

node DP(int i,bool up,bool pre0){
	if(i>19)return {1,0};
	if(!up&&!pre0&&viss[i])return dp[i];
	int r=up?a[i]:9;
	node res={0,0};
	for(int k=0;k<=r;k++){
		if(k==0&&!pre0)continue;
		node add=DP(i+1,up&(k==r),pre0&(k==0));
		(res.num+=add.num)%=Mod;
		(res.sum+=(add.num*pow10[19-i]%Mod*k%Mod+add.sum)%Mod)%=Mod;
	}
	if(!up&&!pre0)viss[i]=1,dp[i]=res;
	return res;
}

int solve(int x){
	if(x==0)return 0;
	for(int i=19;i>=1;i--)a[i]=x%10,x/=10;
	return F(1,K,1,1).sum;
}

int work(int x){
	int p=x%Mod*((x+1)%Mod)%Mod*10060214ll%Mod;
	if(x==0)return 0;
	for(int i=19;i>=1;i--)a[i]=x%10,x/=10;
	return p-DP(1,1,1).sum;
}

signed main(){
	scanf("%lld",&T);
	pow10[0]=1;
	for(int i=1;i<=19;i++)pow10[i]=pow10[i-1]*10%Mod;
	pre(2,1,18);
	sort(lsh+1,lsh+tp+1);
	tot=unique(lsh+1,lsh+tp+1)-lsh-1;
	for(int i=1;i<=tot;i++)mp[lsh[i]]=i;
	for(int i=1;i<=tot;i++){
		for(int j=1;j<=9;j++){
			if(lsh[i]%j!=0)continue;
			to[i][j]=mp[lsh[i]/j];
		}
	}
	while(T--){
		scanf("%lld%lld%lld",&A,&B,&K);
		K=mp[K];
		if(K!=1)printf("%lld\n",((solve(B)-solve(A-1))%Mod+Mod)%Mod);
		else printf("%lld\n",((work(B)-work(A-1))%Mod+Mod)%Mod);
	}
	return 0;
}