#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define ld long double
typedef vector<int> vi;
typedef multiset<int> mi;
typedef multiset<ll> mll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef set<ll> sll;
typedef vector<vector<int>> _2vi;
typedef vector<vector<ll>> _2vll;
#define all(v) ((v).begin()), ((v).end())
#define sz(v) ((ll)((v).size()))

#define vinp(v, n)                \
    for (ull i = 0; i < (n); i++) \
    cin >> (v)[i]
#define printv(v)      \
    for (auto i : (v)) \
    cout << i << " "
#define fr0(i, n) for (ull(i) = 0; (i) < (n); (i)++)
#define fr1(i, n) for (ull(i) = 1; (i) < (n); (i)++)
#define fr(i, x, n) for (ull(i) = (x); (i) < (n); (i)++)
#define _CRT_SECURE_NO_WARNING
const ll MOD = 1000000007;

void Bustany() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
#endif
}

const ll N = 1e5 + 5;
vector<sll> adj(N);
//_2vll adj(N,vll(N));
//vb vis;
string a, b;

ll dp[19][163][163][2][2];
int vis[19][163][163][2][2];

int g = 0;

/*
 ? Find all prime numbers from 1 to n
 ? Complexity : O[n * log(log(n))]
 */
vector<bool> isPrime(205, 1);

vector<int> primes;

vector<int> sieve(int n) {
    isPrime[0] = isPrime[1] = 0;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
        }
    }
    for (int i = 2; i < 163; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

int s = 0;

ll rec(int ind, int mod, int sum, bool greater, bool smaller) {
    if (ind == b.size()) {
        return mod == 0 && sum == s;
    }
    auto &res = dp[ind][mod][sum][greater][smaller];
    if (vis[ind][mod][sum][greater][smaller] == g)return res;
    vis[ind][mod][sum][greater][smaller] = g;
    res = 0;
    ll en = 9, st = 0;
    if (!greater)st = a[ind] - '0';
    if (!smaller)en = b[ind] - '0';
    for (ll i = st; i <= en; i++) {
        if (sum + i <= s)
            res += rec(ind + 1, (mod * 10 + i) % s, sum + i, greater || i > st, smaller || i < en);
    }
    return res;
}


void solve() {
    cin >> a >> b;
    while (a.size() < b.size()) {
        a = '0' + a;
    }
    ll sum = 0;
    for (int i = 0; i < primes.size(); i++) {
        g++;
        s = primes[i];
        sum += rec(0, 0, 0, 0, 0);
    }
    cout << sum << '\n';
}

int main() {
    Bustany();
    sieve(200);
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}