LUCIFER spoj (digit dp)

///:-)
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define inf 2000000000
#define infLL 9000000000000000000
#define infULL 18446744073709551615
#define Aktaruzzaman using
#define pi (2.0*acos(0.0))
#define Pramanik namespace std;
#define vsort(v)   sort(v.begin(),v.end())
#define ull unsigned long long int
#define mem(a, b) memset(a, b, sizeof a)
#define cf 100009
#define MOD 1000000007
#define pii pair<int, int>

//int dx[]={0,1,0,-1};
//int dy[]={1,0,-1,0};
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template< class T > inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
template <class T> inline T is_prime(T a){if(a<2|a==4)return false;if(a==2||a==3||a==5)return true; T g=(T)sqrt(a)+1; for(T i=2; i<=g; i++){if(a%i==0)return false;}return false;}
template <class T> inline T bigmod(T n,T p,T m){if(p==0)return 1; if(p%2)return ((n%m)*bigmod(n,p-1,m))%m; else {T c=bigmod(n,p/2,m);return ((c%m)*(c%m))%m;}}

Aktaruzzaman Pramanik
ll vis[11][85][85][3];
ll prm[102];
ll a[12];
void sv()
{
    prm[0]=1;prm[1]=1;
    for(ll i=2; i<=100; i++){
        if(prm[i]==0){
            for(ll j = i*2; j<=100; j+=i){
                prm[j]=1;
            }
        }
    }
}

ll dp(ll pos, ll choto, ll osum, ll esum)
{
    if(pos==0){
        if(esum>osum && prm[esum-osum]==0)return 1ll;
        return 0;
    }
    if(vis[pos][osum][esum][choto]!=-1)return vis[pos][osum][esum][choto];

    ll xx=0, hi, pp;

    if(choto==1)hi = a[pos];
    else hi=9;

    for(ll i=0; i<=hi; i++){
           if(pos%2==0){
            if(choto==1 && i==hi)xx+=dp(pos-1, 1,  osum, esum+i);
            else xx+=dp(pos-1, 0, osum, esum+i);
           }
           else{
             if(choto==1 && i==hi)xx+=dp(pos-1, 1,  osum+i, esum);
            else xx+=dp(pos-1, 0, osum+i, esum);
           }

    }

    return vis[pos][osum][esum][choto]= xx;

}

int main()

{
    ios_base:: sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    ll t, i, j, k, l, r, x, y, sz;

    cin>>t;
    sv();

    while(t--){
        cin>>l>>r;
        k = l-1;
        sz=0;
        while(k>0){
            a[++sz]=k%10ll;
            k/=10ll;
        }

        mem(vis, -1);
        x = dp(sz, 1, 0, 0);


        sz = 0;
        k = r;
        while(k>0){
            a[++sz] = k%10ll;
            k/=10ll;
        }
//        for(ll i = sz; i>=1; i--)cout<<a[i];
//        cout<<endl;
        mem(vis, -1);
        y = dp(sz, 1, 0, 0);
        cout<<y-x<<endl;
    }



}