Fancy That!

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector <ll> digits;
ll dp[12][2][2][2];

ll calcDP (ll idx, ll parity, ll flag, ll started) {
    if (idx == (ll) digits.size())
        return parity == 0;

    if (dp[idx][parity][flag][started] != -1)
        return dp[idx][parity][flag][started];

    ll res = 0;
    if (started) {
        if (!flag) {
            for (ll i = digits[idx] - 1; i >= 0; i--)
                res += calcDP (idx + 1, parity, 1, 1);
            res += calcDP (idx + 1, parity, 0, 1);
        } else {
            for (ll i = 0; i <= 9; i++)
                res += calcDP (idx + 1, parity, 1, 1);
        }

        return dp[idx][parity][flag][started] = res;
    }

    if (!flag) {
        for (ll i = digits[idx] - 1; i >= 0; i--)
            res += calcDP (idx + 1, i % 2, 1, i != 0);
        res += calcDP (idx + 1, digits[idx] % 2, 0, digits[idx] != 0);
    } else {
        for (ll i = 0; i <= 9; i++)
            res += calcDP (idx + 1, i % 2, 1, i != 0);
    }

    return dp[idx][parity][flag][started] = res;
}

ll get (ll x) {
    digits.clear();
    memset (dp, -1, sizeof (dp));

    while (x) {
        digits.push_back (x % 10);
        x /= 10;
    }

    reverse (digits.begin(), digits.end());
    return calcDP (0, 0, 0, 0);
}

int main () {
    ll t;
    cin >> t;

    while (t--) {
        ll l, r;
        cin >> l >> r;

        //cout << get (l) << ' ' << get (r) << "\n";
        cout << get (r) - get (l - 1) << "\n";
    }

    return 0;
}