#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr int N = 1e6;

void solve() {
    vector<ll> pw10(15);
    pw10[0] = 1;
    for(int i = 1; i < 15; i++) pw10[i] = pw10[i - 1] * 10;
    auto sign = [&](int dig) { return dig % 2 ? -1 : 1; };
    vector h(15, vector(31, 0ll)), p(15, vector(31, 0ll));
    h[0][15] = 1;
    for(int i = 0; i < 14; i++) {
        for(int j = 0; j <= 30; j++) {
            if(h[i][j]) {
                h[i + 1][j + 1] += h[i][j] * 5;
                h[i + 1][j - 1] += h[i][j] * 5;
            }
        }
    }
    {
        vector h(15, vector(31, array<ll, 2>{0, 0}));
        h[0][15][0] = 1;
        for(int i = 0; i < 14; i++) {
            for(int j = 0; j <= 30; j++) {
                if(h[i][j][0]) {
                    h[i + 1][j][0] += h[i][j][0];
                    h[i + 1][j + 1][1] += h[i][j][0] * 4;
                    h[i + 1][j - 1][1] += h[i][j][0] * 5;
                    p[i][j] += h[i][j][0];
                }
                if(h[i][j][1]) {
                    h[i + 1][j + 1][1] += h[i][j][0] * 5;
                    h[i + 1][j - 1][1] += h[i][j][0] * 5;
                    p[i][j] += h[i][j][1];
                }
            }
        }
    }
    for(int i = 0; i <= 14; i++) {
        for(int j = 30; j; j--) {
            h[i][j - 1] += h[i][j];
            p[i][j - 1] += p[i][j];
        }
    }
    auto g = [&](ll r, ll x) {
        ll res = 0;
        for(int i = 12, ty = 0; i >= 0; i--) {
            int dig = r / pw10[i] % 10;
            if(dig) {
                if(ty) { // has >0
                    res += ((dig + 1) / 2) * h[i][15 + x - 1];
                    res += (dig / 2) * h[i][15 + x + 1];
                } else {
                    res += ((dig - 1) / 2) * h[i][15 + x - 1];
                    res += p[i][15 + x];
                    res += (dig / 2) * h[i][15 + x + 1];
                }
                ty = 1;
            }
            if(ty) x -= sign(dig);
        }
        return res + (x < 0);
    };
    auto f = [&](ll l, ll r, ll x) {
        // cerr << l << ' ' << r << ' ' << x << '\n';
        return g(r, x) - g(l - 1, x);
    };
    vector<ll> x(N + 2), s(N + 1), t(N + 1);
    // cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
    for(ll i = 1; i <= N; i++) {
        x[i] = i * i;
        t[i] = 1;
        for(ll j = i; j; j /= 10) t[i] -= sign(j % 10);
    }
    x[N + 1] = ll(1e12) + 1;
    for(int i = 1; i <= N; i++) {
        s[i] = s[i - 1] + f(x[i], x[i + 1] - 1, t[i]);
    }
    // cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
    // for(int i = 1; i <= 10; i++) {
    //     cerr << x[i] << ' ' << s[i] << ' ' << t[i] << '\n';
    // }
    // for(int i = 1; i <= 40; i++) {
    //     int x = i, sq = sqrt(i);
    //     int cnt = 0;
    //     while(x) cnt += sign(x % 10), x /= 10;
    //     while(sq) cnt += sign(sq % 10), sq /= 10;
    //     cerr << i << ' ' << (cnt > 0) << '\n';
    // }
    int q; cin >> q;
    while(q--) {
        ll l, r;
        cin >> l >> r;
        int xl = lower_bound(x.begin(), x.end(), l) - x.begin();
        int xr = prev(upper_bound(x.begin(), x.end(), r)) - x.begin();
        ll ans = s[xr - 1] - s[xl - 1];
        if(l < x[xl]) ans += f(l, x[xl] - 1, t[xl - 1]);
        if(x[xr] <= r) ans += f(x[xr], r, t[xr + 1]);
        cout << ans << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}