思路：典型的数位DP！！！
dp[i][j][k]:第i位，对mod取余为j，数字和对mod取余为k。
注意：由于32位数字和小于95，所以当k>=95时，结果肯定为0.
这样数组就可以开小点，不会超内存！！
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int dp[][][],bit[],k;
int dfs(int pos,int m,int s,bool f)
{
if(pos==-) return !m&&!s;
if(!f&&dp[pos][m][s]!=-) return dp[pos][m][s];
int ans=;
int e=f?bit[pos]:;
for(int i=;i<=e;i++){
ans+=dfs(pos-,(*m+i)%k,(s+i)%k,f&&i==e);
}
if(!f) dp[pos][m][s]=ans;
return ans;
}
int cal(int n)
{
int m=;
while(n){
bit[m++]=n%;
n/=;
}
return dfs(m-,,,);
}
int main()
{
int t,ca=,a,b,ans;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&b,&k);
memset(dp,-,sizeof(dp));
if(k>=) ans=;
else ans=cal(b)-cal(a-);
printf("Case %d: %d\n",++ca,ans);
}
return ;
}