#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include<cmath>
using namespace std;
int plist[10000],pcount=0;
int su(int n)
{
    for(int i=2; i<=sqrt(n); i++)
        if(n%i==0)
            return 0;
    return 1;
}
int main()
{
int a[]={3 , 5 , 13 , 37 , 61 , 73 , 157 , 193 , 277 , 313 , 397 , 421 , 457 , 541 , 613 , 661 , 673 , 733 , 757 , 877 , 997 , 1093 , 1153 , 1201 , 1213 , 1237 , 1321 , 1381 , 1453 , 1621 , 1657 , 1753 , 1873 , 1933 , 1993 , 2017 , 2137 , 2341 , 2473 , 2557 , 2593 , 2797 , 2857 , 2917 , 3061 , 3217 , 3253 , 3313 , 3517 , 3733 , 4021 , 4057 , 4177 , 4261 , 4273 , 4357 , 4441 , 4561 , 4621 , 4933 , 5077 , 5101 , 5113 , 5233 , 5413 , 5437 , 5581 , 5701 , 6037 , 6073 , 6121 , 6133 , 6217 , 6337 , 6361 , 6373 , 6637 , 6661 , 6781 , 6997 , 7057 , 7213 , 7393 , 7417 , 7477 , 7537 , 7753 , 7933 , 8053 , 8101 , 8221 , 8317 , 8353 , 8461 , 8521 , 8677 , 8713 , 8893 , 9013 , 9133 , 9181 , 9241 , 9277 , 9601 , 9661 , 9721 , 9817 , 9901 , 9973 , 10333 , 10357 , 10453 , 10837 , 10861 , 10957 , 11113 , 11161 , 11317 , 11497 , 11677 , 11701 , 12073 , 12157 , 12241 , 12301 , 12421 , 12433 , 12457 , 12541 , 12553 , 12601 , 12721 , 12757 , 12841 , 12853 , 13093 , 13381 , 13417 , 13681 , 13921 , 13933 , 14437 , 14593 , 14737 , 14821 , 15013 , 15073 , 15121 , 15241 , 15277 , 15361 , 15373 , 15733 , 15901 , 16033 , 16333 , 16381 , 16417 , 16573 , 16633 , 16657 , 16921 , 17041 , 17053 , 17077 , 17257 , 17293 , 17377 , 17881 , 18013 , 18097 , 18133 , 18181 , 18217 , 18253 , 18301 , 18313 , 18397 , 18481 , 18553 , 18637 , 18793 , 19237 , 19441 , 19477 , 19717 , 19801 , 19813 , 19861 , 20353 , 20533 , 20641 , 20857 , 21001 , 21061 , 21193 , 21277 , 21313 , 21577 , 21661 , 21673 , 21817 , 22093 , 22501 , 22573 , 22621 , 22993 , 23053 , 23173 , 23557 , 23677 , 23773 , 23917 , 24097 , 24421 , 24481 , 24781 , 24841 , 25033 , 25153 , 25237 , 25561 , 25657 , 25933 , 26017 , 26293 , 26317 , 26437 , 26497 , 26821 , 26833 , 26881 , 26953 , 27073 , 27253 , 27337 , 27361 , 27457 , 27997 , 28057 , 28297 , 28393 , 28813 , 28837 , 28921 , 29101 , 29473 , 29641 , 30181 , 30241 , 30517 , 30553 , 30577 , 30637 , 30661 , 30697 , 30781 , 30853 , 31081 , 31237 , 31321 , 31333 , 31357 , 31477 , 31573 , 31873 , 31981 , 32173 , 32377 , 32497 , 32533 , 32833 , 33037 , 33301 , 33457 , 33493 , 33757 , 33961 , 34057 , 34213 , 34273 , 34381 , 34513 , 34897 , 34981 , 35317 , 35521 , 35677 , 35977 , 36097 , 36241 , 36433 , 36457 , 36793 , 36877 , 36901 , 36913 , 37273 , 37321 , 37357 , 37573 , 37717 , 37957 , 38281 , 38461 , 38833 , 38953 , 38977 , 39217 , 39373 , 39397 , 39733 , 40093 , 40177 , 40213 , 40693 , 40813 , 41017 , 41221 , 41281 , 41413 , 41617 , 41893 , 42061 , 42337 , 42373 , 42793 , 42961 , 43117 , 43177 , 43201 , 43321 , 43573 , 43597 , 43633 , 43717 , 44053 , 44101 , 44221 , 44257 , 44293 , 44893 , 45061 , 45337 , 45433 , 45481 , 45553 , 45613 , 45841 , 46021 , 46141 , 46261 , 46861 , 46993 , 47017 , 47161 , 47353 , 47521 , 47533 , 47653 , 47713 , 47737 , 47797 , 47857 , 48121 , 48193 , 48337 , 48673 , 48757 , 48781 , 49033 , 49261 , 49393 , 49417 , 49597 , 49681 , 49957 , 50221 , 50341 , 50377 , 50821 , 50893 , 51157 , 51217 , 51241 , 51481 , 51517 , 51637 , 52057 , 52081 , 52237 , 52321 , 52453 , 52501 , 52813 , 52861 , 52957 , 53077 , 53113 , 53281 , 53401 , 53917 , 54121 , 54133 , 54181 , 54217 , 54421 , 54517 , 54541 , 54673 , 54721 , 54973 , 55057 , 55381 , 55501 , 55633 , 55837 , 55921 , 55933 , 56053 , 56101 , 56113 , 56197 , 56401 , 56437 , 56701 , 56773 , 56821 , 56857 , 56893 , 57073 , 57097 , 57193 , 57241 , 57373 , 57457 , 57853 , 58153 , 58417 , 58441 , 58537 , 58573 , 58693 , 59053 , 59197 , 59221 , 59281 , 59341 , 59833 , 60217 , 60337 , 60373 , 60637 , 60733 , 60937 , 61057 , 61153 , 61261 , 61297 , 61561 , 61657 , 61681 , 61717 , 61861 , 62137 , 62473 , 62497 , 62533 , 62653 , 62773 , 63313 , 63397 , 63541 , 63697 , 63781 , 63913 , 64153 , 64237 , 64381 , 64513 , 64717 , 65173 , 65293 , 65413 , 65437 , 65497 , 65557 , 65677 , 65881 , 66301 , 66361 , 66601 , 66697 , 66853 , 66973 , 67057 , 67153 , 67273 , 67477 , 67537 , 67741 , 67777 , 67933 , 67993 , 68113 , 68281 , 68521 , 68737 , 69001 , 69073 , 69457 , 69493 , 69697 , 69877 , 70117 , 70177 , 70297 , 70501 , 70621 , 70921 , 70981 , 71233 , 71341 , 71353 , 71593 , 71821 , 72073 , 72481 , 72613 , 72901 , 72937 , 73141 , 73417 , 73477 , 73561 , 73693 , 74077 , 74317 , 74377 , 74713 , 75013 , 75133 , 75181 , 75721 , 75793 , 75913 , 76333 , 76561 , 76597 , 76753 , 77137 , 77641 , 78157 , 78193 , 78277 , 78877 , 78901 , 79333 , 79357 , 79537 , 79657 , 79693 , 79801 , 79873 , 80077 , 80173 , 80221 , 80473 , 80701 , 80713 , 80917 , 81013 , 81181 , 81517 , 81637 , 81853 , 82021 , 82153 , 82261 , 82561 , 82981 , 83077 , 83221 , 83233 , 83437 , 83617 , 83701 , 83773 , 84121 , 84313 , 84673 , 84697 , 84793 , 84913 , 85297 , 85333 , 85453 , 85717 , 85933 , 86353 , 86413 , 87181 , 87253 , 87337 , 87421 , 87433 , 87517 , 87553 , 87973 , 88117 , 88177 , 88237 , 88261 , 88513 , 88741 , 88897 , 88993 , 89293 , 89833 , 89917 , 90121 , 91081 , 91381 , 91393 , 91513 , 91957 , 92041 , 92557 , 92761 , 92821 , 92893 , 92941 , 93097 , 93133 , 93493 , 93637 , 93913 , 94033 , 94117 , 94273 , 94321 , 94441 , 94573 , 94777 , 94837 , 94993 , 95257 , 95317 , 95401 , 95581 , 95617 , 95713 , 95737 , 96097 , 96157 , 96181 , 96493 , 96517 , 96973 , 97081 , 97177 , 97501 , 97561 , 97777 , 97813 , 98017 , 98737 , 98953 , 99277 , 99577 , 99661 , 99877};
    int T,L,R;
    scanf("%d",&T);
    while(T--)
    {
       int sum1,sum2;
       sum1=sum2=0;
        scanf("%d%d",&L,&R);
        for(int i=0;i<=671;i++)
        {
            if(a[i]<L)
                sum1++;
        }
        for(int i=0;i<=671;i++)
        {
            if(a[i]<=R)
                sum2++;
        }
        printf("%d\n",sum2-sum1);


    }

   /* int t=0;
    for(int i=3;i<=99999;i+=2)
    {
        if(su(i)&&su((i+1)/2))
        {
             printf("%d , ",i);
             t++;
        }


    }
printf("\n%d\n",t);*/

    return 0;
}


Measured memory_bytes: 768