F - X mod f(x) (15-12)

#include <iostream>
#include <algorithm>
#include <string.h>

#define int64_t long long
using namespace std;

int L, R;
int dp[11][82][82][82];
vector<int> digit;

int getNum(int pos, int mod, int sum, int digmod, bool limit) {
    if(pos == -1)
        return sum == mod && digmod == 0;

    if(dp[pos][mod][sum][digmod] != -1 && !limit)
        return dp[pos][mod][sum][digmod];

    int res = 0;

    for(int i = 0; i <= 9; ++i) {
        if(limit && i > digit[pos]) break;

        int newLimit = limit && i == digit[pos];
        res += getNum(pos - 1, mod, sum + i, (digmod*10+i) % mod, newLimit);
    }

    if(!limit)
        dp[pos][mod][sum][digmod] = res;

    return res;
}

int64_t solve(int x) {
    digit.clear();
    while(x) {
        digit.push_back(x % 10);
        x /= 10;
    }

    int64_t ans = 0;
    for(int i = 1; i <= 81; ++i)
        ans += getNum(digit.size() - 1, i, 0, 0, true);

    return ans;
}

int main() {
#ifdef DN
    //freopen("in.txt", "r", stdin);
#endif
    //freopen("F-X mod f(x).inp", "r", stdin);
    //freopen("F-X mod f(x).out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= t; ++i) {
        cin >> L >> R;

        cout << "Case " << i << ": " << solve(R) - solve(L - 1) << '\n';
    }

    return 0;
}