#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;
}