萌新求教，时间复杂度应该是对的啊，为何tle

#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstring>

using namespace std;

int cas;

long long read()
{
    long long x=0;char ch=getchar();
    while (!isdigit(ch))ch=getchar();
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x;
}

char out[2000050],*o=out;

void print(long long x)
{
    char buf[23],*b=buf;
    if(!x)*b++=48;
    while(x)*b++=x%10+48,x/=10;
    while(b--!=buf)*o++=*b;
    *o++='\n';
}

long long gcd(long long a,long long b)
{
    return (!b)?a:gcd(b,a%b);
}

long long lcm(long long a,long long b)
{
    if (a==0) return b;
    if (b==0) return a;
    return a*b/gcd(a,b);
}

int dig[20];

long long dp[20][2525][55];

int idx[2525],cnt=0;

long long dfs(long long n,long long r,long long c,bool flag)
{
    //cout << n << " " << r << " " << c << " " << flag << endl;
    if (n==0)
        return r%c==0;
    int tmp=idx[c];
    if (dp[n][r][tmp]!=-1 && !flag)
        return dp[n][r][tmp];
    long long ret=0;
    int ub=flag?dig[n]:9;
    for (int i=0;i<=ub;i++)
        ret+=dfs(n-1,(10*r+i)%2520,lcm(c,i),flag && i==ub);
    if (!flag)
        dp[n][r][tmp]=ret;
    return ret;
}

long long Count(long long a)
{
    int len=0;
    while (a)
    {
        dig[++len]=a%10;
        a/=10;
    }
    return dfs(len,0,1,true);
}

void Init()
{
    for (int i=1;i<=2520;i++)
        if (2520%i==0)
            idx[i]=++cnt;
}

int main()
{
    Init();
    cas=read();
    while (cas--)
    {
        long long l,r;
        cin >> l >> r;
        memset(dp,-1,sizeof(dp));
        long long R=Count(r);
        //memset(dp,-1,sizeof(dp));
        long long L=Count(l-1);
        cout << R-L << endl;
    }
    return 0;
}