1 //首先要求能被各位上的数整除，可以转化为被一个数整除问题。

 2 //这个数就是各位上数的最小公倍数LCM（不是GCD）。

 3 //其次，处理整除问题，得转化成数位DP的余数模板。1~9的LCM最大是2520, 那么%2520,让其可以开数组进行记忆化搜索。

 4 //最后, 对于不能%2520最后结果，再%各个数位累计过来的LCM。

 5 //这样下来，需要开20*2520*2520的数组，往CF上一交你会发现MLE。

 6 //仔细观察每次的LCM，其范围是1~2520没错，但是都是整除gcd的结果（LCM=a*b/gcd(a,b) ），也就是说所有LCM都是某个数的约数。

 7 //这个数其实就是2520。所以DP之前，为2520打个表，把LCM给离散化Hash。这样其实只有48个LCM了。数组开20*2520*50即可。

 8 //注意结果是int64。

 9 #include<stdio.h>

10 #include<string.h>

11 #include<algorithm>

12 #include<iostream>

13 #include<map>

14 using namespace std;

15 const int maxn=20;

16 const int mod=2520;

17 typedef long long ll;

18 ll v[maxn],dp[maxn][mod+50][50];

19 map<ll,ll>w;

20 ll lcm(ll a,ll b)

21 {

22     ll ans=min(a,b);

23     while(ans)

24     {

25         if(a%ans==0 && b%ans==0) break;

26         ans--;

27     }

28     return (a*b)/ans;

29 }

30 ll dfs(ll pos,ll sum,ll sta,bool limit)

31 {

32     if(sta==0)return 0;

33     if(pos==-1)

34     {

35         return sum%sta==0;

36     }

37     if(!limit && dp[pos][sum][w[sta]]!=-1) return dp[pos][sum][w[sta]];

38     ll up=limit?v[pos]:9;

39     ll tmp=0;

40     for(ll i=0;i<=up;++i)

41     {

42         if(i>0)

43         {

44             tmp+=dfs(pos-1,(sum*10+i)%mod,lcm(sta,i),limit && i==v[pos]);

45

46         }

47         else tmp+=dfs(pos-1,(sum*10+i)%mod,sta,limit && i==v[pos]);

48     }

49     if(!limit) dp[pos][sum][w[sta]]=tmp;

50     //只有上界为9的时候才会往dp数组里面存，因为这样能节省更多的时间

51     return tmp;

52 }

53 ll solve(ll ans)

54 {

55     ll pos=0;

56     while(ans)

57     {

58         v[pos++]=ans%10;

59         ans/=10;

60     }

61     return dfs(pos-1,0,1,true);

62 }

63 int main()

64 {

65     ll t,l,r,m=0;

66     scanf("%I64d",&t);

67     for(ll i=1;i<=mod;++i)

68     {

69         if(mod%i==0)

70         {

71             ++m;

72             w[i]=m;

73         }

74     }

75     memset(dp,-1,sizeof(dp));

76     while(t--)

77     {

78         scanf("%I64d%I64d",&l,&r);

79         printf("%I64d\n",solve(r)-solve(l-1));

80     }

81     w.clear();

82     return 0;

83 }