1     #include 
     
       2     #include 
      
        3     #include 
       
         4     #include 
        
          5     #include 
         
           6     #include 
          
            7 8 using namespace std; 9 10 #define LL long long11 const int MOD = 2520;12 LL dp[20][50][2550];13 int a[20];14 int Hash[2550];15 16 LL gcd(LL a, LL b)17 {18 return b?gcd(b,a%b):a;19 }20 21 LL dfs(int pos, int num, int lcm, bool limit)22 {23 if(-1==pos) return num%lcm == 0;24 if(!limit && ~dp[pos][Hash[lcm]][num]) return dp[pos][Hash[lcm]][num];25 LL ans = 0;26 int end = limit?a[pos]:9;27 for(int i=0; i<=end; i++)28 ans += dfs(pos-1, (num*10+i)%MOD, i?lcm*i/gcd(lcm,i):lcm, limit&&i==a[pos]);29 if(!limit) dp[pos][Hash[lcm]][num] = ans;30 return ans;31 }32 33 LL solve(LL n)34 {35 int pos = 0;36 while(n)37 {38 a[pos++] = n%10;39 n /= 10;40 }41 return dfs(pos-1, 0, 1, 1);42 }43 44 int main()45 {46 int T;47 scanf("%d", &T);48 int cnt = 0;49 for(int i=1; i<=MOD; i++)50 if(MOD%i == 0)51 Hash[i] = cnt++;52 memset(dp, -1, sizeof(dp));53 while(T--)54 {55 long long l, r;56 scanf("%lld%lld", &l, &r);57 printf("%lld\n", solve(r)-solve(l-1));58 }59 return 0;60 }