1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

const int MOD = 2520;
ll dp[20][2520][50];
int id[2521];
vi lcms;
void init() {
    memset(dp, -1, sizeof(dp));
    rep(i, 1, MOD) {
        if (MOD % i == 0) {
            id[i] = sz(lcms);
            lcms.push_back(i);
        }
    }
    return;
}
void solve() {
    int t;
    cin >> t;
    init();
    string num1, num2;
    map<tri, ll> ma;
    rep(i, 0, t - 1) {
        cin >> num1 >> num2;
        int n = num2.length();
        int dif = n - num1.length();
        auto dfs = [&](this auto&& dfs, int cnt, int s, int lm, bool limit_low, bool limit_high) -> ll {
            if (cnt == n) return s % lm == 0;
            if (!limit_low && !limit_high && dp[n - cnt][s][id[lm]] != -1) return dp[n - cnt][s][id[lm]];
            ll res = 0;
            int lo = limit_low && cnt >= dif ? num1[cnt - dif] - '0' : 0;
            int hi = limit_high ? num2[cnt] - '0' : 9;
            int d = lo;
            if (limit_low && cnt < dif) {
                res += dfs(cnt + 1, s, lm, true, false);
                d = 1;
            }
            for (; d <= hi; d++) {
                int ns = (s * 10 + d) % MOD;
                int nlm = lm;
                if (d != 0) nlm = lm / __gcd(lm, d) * d;
                res += dfs(cnt + 1, ns, nlm, limit_low && d == lo, limit_high && d == hi);
            }
            if (!limit_high && !limit_low) dp[n - cnt][s][id[lm]] = res;
            return res;
        };
        cout << dfs(0, 0, 1, true, true) << endl;
    }
    return;
}