#include <cstdio>
#include <vector>
#include <algorithm>

const int maxn = 1e8 + 5;

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

int main(){
    
    int T,l,r;
    std::vector <int> ans;
    std::vector <bool> a(maxn,1);
    
    scanf("%d",&T);
    a[0] = a[1] = 0;
    for (int i = 2;i * i <= maxn;i++)
        if (a[i])
            for (int j = i * 2;j <= maxn;j += i)
                a[j] = 0;
    for (int i = 2;i <= maxn;i++) 
        if (a[i] && a[f(i)])
            ans.push_back(i);
    while (T--)
        scanf("%d%d",&l,&r),
        printf("%d\n",upper_bound(ans.begin(),ans.end(),r) - ans.begin() - (lower_bound(ans.begin(),ans.end(),l) - ans.begin()));
    
    return 0;
}

最长是814ms