如果一个数能够被组成它的各个非0数字整除，则称它是完美数。例如：1-9都是完美数，10,11,12,101都是完美数，但是13就不是完美数（因为13不能被数字3整除）。
现在给定正整数x,y，求x和y之间（包含x和y的闭区间）共有多少完美数。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数，X, Y中间用空格分割。(1 <= X <= Y <= 10^18)
Output
输出共T行，对应区间中完美数的数量。
1..10的lcm为2520，从1..10里选若干个数的lcm个数只有四十多个。。
f[i][j][k]表示十进制下长度为i位的数字里，那个数字模2520后的值为j的倍数，数位上各个非0数字的lcm为第k种。
之后就是正常的数位DP了。
一开始不会做是因为状态表示得不对...第二维没有考虑倍数...结果统计的复杂度就上天了...
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
//#define d double
#define ld long double
const int maxn=,inf=;
ll f[][][];
int NEXT[][],LCM[][],id[],num[];
int i,j,k,n,m,s,t,ans; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while(rx<''&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;
} inline int gcd(int a,int b){return !b?a:gcd(b,a%b);}
inline void pre(){
int i,j,tmp=;
memset(f,,sizeof(f));
for(i=;i<=;i++){
if(!(%i))id[i]=++tmp;
LCM[i][]=LCM[i][]=i;
for(j=;j<=;j++)LCM[i][j]=i*j/gcd(i,j);
}
for(i=;i<;i++)for(j=;j<=;j++)NEXT[i][j]=(i*+j)%;
}
ll dfs(int i,int p,int lcm,bool pr){
if(i<)return !(p%lcm);
if(!pr&&f[i][p][id[lcm]]!=-)return f[i][p][id[lcm]];
int mx=!pr?:num[i];ll tmp=;
for(int j=;j<=mx;j++)
tmp+=dfs(i-,NEXT[p][j],LCM[lcm][j],pr&&j==mx);
if(!pr)f[i][p][id[lcm]]=tmp;
return tmp;
}
inline ll get(ll x){
int len=;while(x)num[len++]=x%,x/=;
return dfs(len-,,,);
}
int main(){
pre();ll l,r;
for(int t=read();t;t--)
scanf("%lld%lld",&l,&r),
printf("%lld\n",get(r)-get(l-));
}