#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define il inline
#define re register

const int MAXN = 1e6+5;

il int f(int x){return x >= 10 ? f(x / 10) + (x % 10) : x;}

int main(){
    
    re bool a[MAXN];
    re int T,l,r,ans;
    
    cin >> T;
    memset(a,1,sizeof(a));
    a[0] = a[1] = 0;
    for (re int i = 2;i * i <= MAXN;i++)
        if (a[i])
            for (re int j = i * 2;j <= MAXN;j += i)
                a[j] = 0;
    while (T--){
        
        ans = 0;
        cin >> l >> r;
        for (re int i = l;i <= r;i++)
            if (a[i] && a[f(i)])
                ans++;
        cout << ans << endl;
        
    }
    
    return 0;
}