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

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

mt19937_64 rng(time(0));

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(61, 0ll)), p(15, vector(61, 0ll));
    h[0][30] = 1;
    for(int i = 0; i < 14; i++) {
        for(int j = 0; j <= 60; 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(61, array<ll, 2>{0, 0}));
        h[0][30][0] = 1;
        for(int i = 0; i < 14; i++) {
            for(int j = 0; j <= 60; 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][1] * 5;
                    h[i + 1][j - 1][1] += h[i][j][1] * 5;
                    p[i][j] += h[i][j][1];
                }
            }
        }
    }
    for(int i = 0; i <= 14; i++) {
        for(int j = 60; 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][30 + x - 1];
                    res += (dig / 2) * h[i][30 + x + 1];
                } else {
                    res += ((dig - 1) / 2) * h[i][30 + x - 1];
                    res += p[i][30 + x];
                    res += (dig / 2) * h[i][30 + x + 1];
                }
                ty = 1;
            }
            if(ty) x -= sign(dig);
        }
        return res + (x <= 0);
    };
    auto f = [&](ll l, ll r, ll x) {
        return g(r, x) - g(l - 1, x);
    };
    vector<ll> x(N + 2), s(N + 1), t(N + 1);
    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]);
    }
    // for(int i = 1; i <= 10; i++) {
    //     cerr << x[i] << ' ' << s[i] << ' ' << t[i] << ' ' << f(x[i], x[i + 1] - 1, t[i]) << '\n';
    // }
    // auto chk = [&](int 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;
    //     return cnt > 0;
    // };
    // for(int i = 1; i <= 200; i++) {
    //     if(chk(i)) cerr << i << ' ';
    // }
    // cerr << '\n';
    // auto bf = [&](int l, int r, int pt = 0) {
    //     int res = 0;
    //     for(int i = l; i <= r; i++) {
    //         res += chk(i);
    //         if(chk(i) && pt) cerr << i << ' ';
    //     }
    //     if(pt) cerr << '\n';
    //     return res;
    // };
    auto calc = [&](ll l, ll r) {
        int xl = upper_bound(x.begin(), x.end(), l) - x.begin() - 1;
        int xr = upper_bound(x.begin(), x.end(), r) - x.begin() - 1;
        ll ans = 0;
        if(xl < xr) {
            ans = s[xr - 1] - s[xl];
            ans += f(l, x[xl + 1] - 1, t[xl]);
            ans += f(x[xr], r, t[xr]);
        } else {
            ans = f(l, r, t[xl]);
        }
        return ans;
    };
    // for(int i = 1; i <= 1000; i++) {
    //     for(int j = i + 1; j <= 1000; j++) {
    //         if(calc(i, j) != bf(i, j)) {
    //             cerr << i << ' ' << j << '\n';
    //             // cerr << i << ' ' << j << ' ' << calc(i, j) << ' ' << bf(i, j) << '\n';
    //             // bf(i, j, 1);
    //             return;
    //         }
    //     }
    // }
    int q; cin >> q;
    while(q--) {
        ll l, r;
        cin >> l >> r;
        cout << calc(l, r) << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}
/*
1 0 2
4 3 0
9 3 2
16 10 0
25 12 2
36 23 0
49 25 2
64 37 0
81 41 2
100 27 1
1 100 22 42
4 6 8 16 18 20 21 22 23 24 26 28 36 38 40 41 42 43 44 45 46 47 48 60 62 64 65 66 67 68 69 70 72 74 76 78 80 82 84 86 88 100


*/