#include<bits/stdc++.h>
#define MAX 1000009
 
using namespace std;
 
bool arr[MAX];
 
vector<int>prime;
 
vector<int>check;
 
void sieve()
{
    int i,j,k;
 
    k = sqrt(MAX);
 
    prime.push_back(2);
 
    for(i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(j=i*i; j<MAX; j+=i+i)
            {
                arr[j]=1;
            }
        }
    }
 
    for(i=3; i<MAX; i+=2)
        if(arr[i]==false)
            prime.push_back(i);
 
    int sz = prime.size();
 
    for(i=0; i<sz; i++)
    {
        string s;
 
        stringstream ss;
 
        ss<<prime[i];
 
        s = ss.str();
 
        int len = s.length();
 
        int sum = 0;
 
        for(j=0; j<len; j++)
        {
            sum+=(s[j]-48);
        }
 
        if(sum==2)
        {
            check.push_back(prime[i]);
        }
        else if(arr[sum]==false && (sum&1))
        {
            check.push_back(prime[i]);
        }
    }
 
    sort(check.begin(),check.end());
}
 
int main()
{
    sieve();
 
    int test,from,to;
 
    scanf("%d",&test);
 
    while(test--)
    {
        scanf("%d%d",&from,&to);
 
        vector<int>::iterator low,high;
 
        low = lower_bound(check.begin(),check.end(),from);
 
        high = upper_bound(check.begin(),check.end(),to);
 
        int res = (high-check.begin())-(low-check.begin());
 
        printf("%d\n",res);
    }
 
    return 0;
}