#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) rep(ghf,SZ(a)){rep(kjh,SZ(a[ghf])){cout<<(a[ghf][kjh]<10?" ":"")<<a[ghf][kjh]<<" ";}ENDL;}
#define out(a) cout<<(a)<<endl
#define fi first
#define se second
#define Vec vector
#define P pair
typedef long long ll;
typedef string str;
typedef vector<ll> V;
typedef pair<ll,ll> Pi;
typedef vector<Pi> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int max(int a,int b){if(a>b)return a; return b;}
int min(int a,int b){if(a>b)return b; return a;}
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

bool sosu(int n){
  bool res=true;
  for(int i=2;i*i<=n;++i){
    if(n%i==0)res=false;
  }
  return res;
}

bool like(int a){
  int b=(a+1)/2;
  return (sosu(a)&&sosu(b));
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  V like2017={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,100153,100237,100621,101161,101173,101197,101293,101341,101533,101641,101977,102001,102061,102121,102217,102301,102337,102397,102433,102481,102841,102877,103357,103573,103657,103813,103981,104053,104113,104161,104473,104773,105253,105277,105613,105673,105913,105997,106033,106297,106321,106537,106753,106801,106957,107053,107101,107137,107581,107713,107761,107773,108301,108553,108637,109201,109357,109441,109453,109597,109897,110017,110233,110437,110581,110821,110881,111217,111637,111697,111973,112261,112297,112621,113017,113341,113557,114073,114193,114277,114601,114661,114913,114973,115057,115117,115201,115561,115657,115693,115981,116113,116257,116293,116341,116461,116833,116881,116953,117133,117373,117541,117577,117841,118057,118213,118297,118681,118717,119233,119557,119617,119773,120181,120277,120577,120661,121321,121357,121453,121621,121921,122053,122761,122833,123121,123217,123373,123433,123457,123637,123757,123817,123853,123973,124021,124693,125737,125941,126397,126421,126481,126493,126733,126781,127081,127297,127453,127597,127681,128341,128377,128461,128473,128761,129757,129841,129853,129901,129937,130021,130057,130201,130477,130513,130873,130957,131041,131101,131113,131293,131413,131437,131617,131701,131797,132541,132721,133201,134257,134437,134677,134857,135301,135601,135613,135637,135781,135913,136417,136453,136621,136657,136777,136897,137077,138493,138517,139393,139753,139861,139981,140197,140221,140281,140401,140473,140593,140617,140761,140977,141073,141241,141277,141697,141937,141961,142237,142381,142573,142657,142837,142873,143053,143137,143413,143617,143797,143833,143881,144037,144061,144541,144757,144961,145477,145633,145777,145861,145897,146077,146581,146617,146701,146833,146917,146941,146953,147397,147541,147793,147997,148153,148201,148513,148573,148633,149053,149101,149173,149521,149713,150217,151141,151153,151237,151357,151561,151573,152077,152197,152293,152461,152941,153073,154057,154081,154333,154753,154981,155017,155137,155317,155377,155461,155521,155593,155797,156061,156157,156241,156601,156733,157081,157141,157393,157561,157837,158077,158293,158617,159073,159097,159157,159337,159553,159721,160141,160441,160681,160813,160981,161053,161221,161341,161521,161977,163117,163633,163861,164341,164377,164413,164677,164701,165133,165181,165313,165397,165457,165673,165877,165961,166273,166597,166861,167113,167437,167521,168253,168457,168697,168781,168913,169177,169501,169837,169933,169957,170293,170473,170761,170857,171253,171637,171673,172021,172153,172321,172357,172573,172681,172741,172933,172981,173713,173917,174241,174673,175081,175261,175393,175621,175753,176353,176521,176641,176677,177217,177301,177481,177493,177601,178141,178417,178537,178897,179041,179317,179533,179593,179833,179917,179953,180001,180241,180541,180793,181693,181813,182473,182593,182617,182773,182821,183877,184081,184153,184441,184633,184693,184753,184837,184957,185137,185161,185533,185557,185641,185797,185917,186301,186397,186481,187273,187477,187573,187897,188017,188197,188401,188437,188653,188701,188953,189061,189493,189697,189901,189997,190261,190573,190633,190837,190921,191137,191161,191413,191461,191473,191833,191977,192193,193201,193393,193513,193573,193597,193813,193861,193957,193993,194353,194653,194917,195121,195157,195457,195541,195697,195973,196033,196081,196201,196453,196501,196597,196837,197773,197893,198277,198553,198733,198817,198937,199153,199321,199357,199417,199657,199741,199753,199813,199921};

  ll Q;
  cin>>Q;

  while(Q--){
    int l,r;
    cin>>l>>r;
    int res=0;
    for(auto&num:like2017)
      if(num>=l && num<=r)res++;
    out(res);
  }

  
  
  
  return 0;
}



Measured memory_bytes: 768