#include <bits/stdc++.h>
#include <stdio.h>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
#define bye return
#define yes cout << "YES" << el;
#define no cout << "NO" << el;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define Shoyo                     \
ios_base::sync_with_stdio(0); \
cin.tie(NULL);
#define ff first
#define ss second
#define pii pair<ll, ll>
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define cl(x, y) (x + y - 1) / y
#define el "\n"
#define os tree<pii, null_type, less<>, \
rb_tree_tag, tree_order_statistics_node_update>
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};
const ll LOG = 20;
const int N = 1e6 + 5;
const ll MOD = 1e9 + 7;
bool is_prime[200];   // عشان نجيب البرايمز
vector<int> primes;
void sieve(int mx) {
    fill(is_prime + 2, is_prime + mx + 1, true);
    for (int i = 2; i * i <= mx; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= mx; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 2; i <= mx; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}
string l,r;
ll vid;
ll v[20][2][2][165][165];
ll mem[20][2][2][165][165];
ll p;
ll dp(ll i,ll le,ll ri,ll sum,ll rem) {
   if (i==r.size()) {
       return (sum==p and rem==0 );
   }
    if (sum>p)return 0;
    ll &res=mem[i][le][ri][sum][rem];
    if (v[i][le][ri][sum][rem]==vid) return res;
    v[i][le][ri][sum][rem]=vid;
    ll st=le?0:l[i];
    ll e=ri?9:r[i];
    res=0;
    for (ll d=st;d<=e;d++) {
        res+=dp(i+1,le or( d>l[i]), ri or (d<r[i]),sum+d,(rem*10+d)%p);
    }
return res;

}
void solve() {
    cin>>l>>r;
    l=string(r.size()-l.size(),'0')+l;
    ll ans=0;
    for (auto &x:l)x-='0';
    for (auto &x:r)x-='0';
    sort(all(primes));
   for (auto z:primes) {
       p=z;
       if (p>167)break;
       vid++;
       ans+=dp(0,0,0,0,0);
   }
cout<<ans<<el;

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