#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define all(a) a.begin(), a.end()
 
string target;
int dp[20][165][1460]; //Another trick, you can remove 'sm' dimension
bool prime[1460];
 
int recur(int pos, bool sm=0, int dsum=0, int dsqsum=0){
    if(pos==-1) return (prime[dsum] and prime[dsqsum]);
 
    int& res = dp[pos][dsum][dsqsum];
    if(sm && res != -1) return res;
 
    int lim = sm?9:target[pos]-'0', ans = 0;
    for(int d = 0; d <= lim; d++)
        ans+=recur(pos-1,sm or d!=lim, dsum+d, dsqsum+d*d);
    return sm ? res = ans : ans;
}
 
bool isprime(int x){
    for(int i = 2; i*i<=x; i++)
        if(x%i==0) return false;
    return true;
}
 
int32_t main()
{
    memset(dp, -1, sizeof(dp));
    for(int i = 2; i < 1460; i++) prime[i]=isprime(i);
    int t; cin >> t;
    while(t--){
        int l, r; cin >> l >> r;
        target = to_string(r); reverse(all(target));
        int tot = recur((int)target.size()-1); 
        target = to_string(l-1); reverse(all(target));
        cout << tot-recur((int)target.size()-1) << "\n";
    }
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpLCBhLmVuZCgpCgpzdHJpbmcgdGFyZ2V0OwppbnQgZHBbMjBdWzE2NV1bMTQ2MF07IC8vQW5vdGhlciB0cmljaywgeW91IGNhbiByZW1vdmUgJ3NtJyBkaW1lbnNpb24KYm9vbCBwcmltZVsxNDYwXTsKCmludCByZWN1cihpbnQgcG9zLCBib29sIHNtPTAsIGludCBkc3VtPTAsIGludCBkc3FzdW09MCl7CiAgICBpZihwb3M9PS0xKSByZXR1cm4gKHByaW1lW2RzdW1dIGFuZCBwcmltZVtkc3FzdW1dKTsKCiAgICBpbnQmIHJlcyA9IGRwW3Bvc11bZHN1bV1bZHNxc3VtXTsKICAgIGlmKHNtICYmIHJlcyAhPSAtMSkgcmV0dXJuIHJlczsKICAgIAogICAgaW50IGxpbSA9IHNtPzk6dGFyZ2V0W3Bvc10tJzAnLCBhbnMgPSAwOwogICAgZm9yKGludCBkID0gMDsgZCA8PSBsaW07IGQrKykKICAgICAgICBhbnMrPXJlY3VyKHBvcy0xLHNtIG9yIGQhPWxpbSwgZHN1bStkLCBkc3FzdW0rZCpkKTsKICAgIHJldHVybiBzbSA/IHJlcyA9IGFucyA6IGFuczsKfQoKYm9vbCBpc3ByaW1lKGludCB4KXsKICAgIGZvcihpbnQgaSA9IDI7IGkqaTw9eDsgaSsrKQogICAgICAgIGlmKHglaT09MCkgcmV0dXJuIGZhbHNlOwogICAgcmV0dXJuIHRydWU7Cn0KCmludDMyX3QgbWFpbigpCnsKICAgIG1lbXNldChkcCwgLTEsIHNpemVvZihkcCkpOwogICAgZm9yKGludCBpID0gMjsgaSA8IDE0NjA7IGkrKykgcHJpbWVbaV09aXNwcmltZShpKTsKICAgIGludCB0OyBjaW4gPj4gdDsKICAgIHdoaWxlKHQtLSl7CiAgICAgICAgaW50IGwsIHI7IGNpbiA+PiBsID4+IHI7CiAgICAgICAgdGFyZ2V0ID0gdG9fc3RyaW5nKHIpOyByZXZlcnNlKGFsbCh0YXJnZXQpKTsKICAgICAgICBpbnQgdG90ID0gcmVjdXIoKGludCl0YXJnZXQuc2l6ZSgpLTEpOyAKICAgICAgICB0YXJnZXQgPSB0b19zdHJpbmcobC0xKTsgcmV2ZXJzZShhbGwodGFyZ2V0KSk7CiAgICAgICAgY291dCA8PCB0b3QtcmVjdXIoKGludCl0YXJnZXQuc2l6ZSgpLTEpIDw8ICJcbiI7CiAgICB9Cn0=

MTAKMSAxMAoxMCAyMAoyMCAzMAo1NyA3MwozMCAzMDAKMTAwIDEwMDAwMAo1MDAwIDUwMDAwCjQ1NTYgMjQzMjQzMjQKMTAwMDAgMzEzMjQzMTI0MzI0NDEKMSAxMDAwMDAwMDAwMDAwMDAwMDAw

10
1 10
10 20
20 30
57 73
30 300
100 100000
5000 50000
4556 24324324
10000 31324312432441
1 1000000000000000000