题目链接：https://www.luogu.com.cn/problem/CF55D
数位dp
解法：所有非零位都能整除这个数，那么就是说这些非零位的公倍数能够整除这个数。
那么按照通常情况我们定义dp数组的时候应该定义成dp[pos][num][gbs]，表示当前枚举到了第几位、上次枚举到的数、之前所有数位的最小公倍数。那么题目范围一共有9e18，第一维只用开20即可，那么第二维显然不能开9e18.第二维我们处理的方法是：既然我们要讨论的是这个num能否被其之前所有非零位的最小公倍数整除，那么所有非零数位的可能只有1-9 共9个数，1-9的最小公倍数是2520.那么我们只需要考虑num%2520的结果能否被最小公倍数整除就行了。因为2520一定能被最小公倍数整除，取模就是把一定能被整除的那些数去掉，剩下的数是不一定能被整除的。
那么第二维只用开2521的大小即可。接下来我们考虑所有公倍数的情况。刚刚我们已经知道1-9 9个数的最小公倍数是2520，那么假如第三维开2521的大小，数组将会达到越近1e8的量级，依然会爆。那么我们考虑将2520的因子离散化。2520的因子有48个，打个表就很容易得出，所以第三维只用开50就行了。这样开数组就不会爆炸了。
那么接下来就是记忆化搜索写法的数位dp的基本操作了，数位dp处理答案使用到的是差分的思想，这个是数位dp的基操。具体见注释。
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//gcd(a,b)=gcd(a,b-a)(b>a);
inline int lcm(int a, int b){return a / gcd(a, b) * b;}//lcm(n,m)=n*m/gcd(n,m)
#define int long long
int dp[30][3000][50];
int lsh[3000];
int a[60];
int dfs(int pos,int lim,int mo,int gbs)
//当前处理第几位，是否有大小限制，当前的值对2520取模的结果，当前的公倍数
{
if(!pos)
{
if(mo%gbs==0) return 1;//如果这个数能够被非零位的公倍数整除那么就统计进答案
else return 0;//否则就不
}
//记忆化搜索
if(!lim&&~dp[pos][mo][lsh[gbs]]) return dp[pos][mo][lsh[gbs]];
int up=lim?a[pos]:9;//上界
int res=0;
for(int i=0;i<=up;i++)
{
res+=dfs(pos-1,lim&&i==up,(mo*10+i)%2520,i!=0?lcm(gbs,i):gbs);
//处理下一位。mo*10+i就是该数加上下一位之后的新的数，加上了非零位的数要更新其公倍数
//在这个数的最后一位加上之前 %2520对答案都没有影响
}
if(!lim) dp[pos][mo][lsh[gbs]]=res;
return res;
}
int calc(int x)
{
memset(a,0,sizeof(a));
int len=0;
while(x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,1,0,1);
//注意，最后gbs这里初始要传1进去，不然更新公倍数的时候会出问题（除0）
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int idx=0;
for(int i=1;i<=2520;i++)
{
if(2520%i==0)
{
lsh[i]=++idx;//把2520的每个因子离散化下来
}
}
int t;
cin>>t;
memset(dp,-1,sizeof(dp));//记忆化搜索需要用到，这一行不能写while(t--)里面
while(t--)
{
int l,r;
cin>>l>>r;
cout<<calc(r)-calc(l-1)<<'\n';
}
return 0;
}