分析
显然是数位 DP，但是要想清楚这个条件怎么处理。
注意到如果 $a_1|d,a_2|d,\cdots,a_k|d$，那么 $\operatorname{lcm}(a_1,a_2,\cdots,a_l)|d$。因此我们只需要知道这个数对每一位上的数的 $\operatorname{lcm}$ 取模的结果。
但是 $\operatorname{lcm}$ 是动态变化的，所以不好直接对 $\operatorname{lcm}$ 取模的结果。因此我们记对 $\operatorname{lcm}(1,2,\cdots,9)=2520$ 取模的结果。
到这里可以设出状态了。根据套路设 $dp_{i,j,k,lim}$ 表示前 $i$ 位对 $2520$ 取模的结果是 $j$，前 $i$ 位上的数的 $\operatorname{lcm}$ 是 $k$，是否顶着上界的方案数。转移什么的就很简单了。
现在有一个问题是这个 DP 数组是开不下的。注意到 $\operatorname{lcm}$ 一定是 $2520$ 的因数，因此第三维的大小实际上只有 $\mathbf{d}(2520)=48$ 。这样子就开得下了。
还有一个问题，就是这样子可能会 TLE on test #11。考虑到所有没有顶着上界的状态的方案数都是一样的，因此我们可以把 $lim$ 一维去掉（即只记忆化没有顶着上界的），这样子每次就可以少算很多状态。然后就可以过了。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;
inline ll read() {
ll X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
int id[2520],fcnt=0;
int a[20],len;
ll dp[20][2520][50];
inline ll __lcm(ll a,ll b) {
if (!a||!b) return a+b;
else return a/__gcd(a,b)*b;
}
inline ll dfs(int p,int r,int lcm,int flag) {
if (p==0) return !(r%lcm);
if (!flag&&(~dp[p][r][id[lcm]])) return dp[p][r][id[lcm]];
int lim=flag?a[p]:9; ll res=0;
for (re int i=0;i<=lim;++i)
res+=dfs(p-1,(r*10+i)%2520,__lcm(i,lcm),flag&(i==lim));
if (!flag) dp[p][r][id[lcm]]=res;
return res;
}
inline ll calc(ll x) { len=0;
while (x) a[++len]=x%10,x/=10;
return dfs(len,0,1,1);
}
int main() {
memset(dp,-1,sizeof(dp));
for (re int i=1;i<=2520;++i)
if (2520%i==0) id[i]=++fcnt;
int T=read();
while (T--) {
ll l=read(),r=read();
printf("%lld\n",calc(r)-calc(l-1));
}
return 0;
}