/**************************************************
****I have been back!
****Because I have a dream!
****That one day I must be that a strong man !
****--------Written by Apllo.
***************************************************/
///#pragma GCC optimize ("O2") ///G++�ã�
///#pragma comment(linker, "/STACK:36777216")///C++��
///#pragma comment(linker, "/STACK:102400000,102400000")///C++�ã���ֹջ���
#include<bits/stdc++.h>
//#include <unordered_map>
//#include <unordered_set>
using namespace std;


#define debug       cout << "***********************" << endl
#define Bug(s)      cout << "s = " << s << endl
#define mem(a,b)    memset(a, b, sizeof(a))
#define lson        l, mid, rt<<1
#define rson        mid + 1, r, rt<<1|1
#define For(i, x, n)  for(int i = (x) ; i < (n) ; ++i)
#define Forr(i, x, n) for(int i = (x) ; i <= (n) ; ++i)
#define Rep(i, x, n)  for(int i = (x) ; i > (n) ; --i)
#define Repp(i, x, n) for(int i = (x) ; i >= (n) ; --i)
#define highint( n )  ceil( n )
#define lowint( n )   floor( n )
#define SERU(x)       floor((double) x + 0.5 )
#define lowbit(x)     (x & (-x))

#define all(x)      (x).begin(), (x).end()
#define SZ(x)       (int)(x).size()
#define FA(i, a, x) for (__typeof((x).begin()) i=(a); i!=(x).end(); ++i)
#define RA(i, x)    FA(i, (x).begin(), x)
#define FDA(i, a, x)  for (__typeof((x).rbegin()) i=(x).rbegin(); i!=(a); ++i)
#define RDA(i, x)   FDA(i, (x).rend(), x)
#define P(v, x)     (v.find(x) != v.end())
#define Pos(v, x)   (find(all(v), x) != v.end())
#define UN(a)       sort(all(a)), a.erase(unique(all(a)), a.end())
#define all(x)      (x).begin(), (x).end()
#define SZ(x)       (int)(x).size()
#define FA(i, a, x) for (__typeof((x).begin()) i=(a); i!=(x).end(); ++i)
#define RA(i, x)    FA(i, (x).begin(), x)
#define FDA(i, a, x)  for (__typeof((x).rbegin()) i=(x).rbegin(); i!=(a); ++i)
#define RDA(i, x)   FDA(i, (x).rend(), x)
#define P(v, x)     (v.find(x) != v.end())
#define Pos(v, x)   (find(all(v), x) != v.end())
#define UN(a)       sort(all(a)), a.erase(unique(all(a)), a.end())
#define REV(a)      reverse(all(a))
#define mp(a, b)    make_pair(a, b)
#define p(a, b)     pair<int, int>(a, b)
#define sf1i(x)     scanf("%d", &x)
#define sf1l(x)     scanf("%I64d", &x)
#define sf2i(x, y)  scanf("%d%d", &x, &y)
#define sf2l(x, y)  scanf("%I64d%I64d", &x, &y)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ll long long
#define eps 1e-8


typedef pair<int, int> pii;
typedef vector< int > vi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector< vi > mati;
typedef vector< vl > matl;
typedef vector< double > vd;
typedef vector< string > vs;
typedef complex< double > cp;
typedef istringstream ISS;
typedef ostringstream OSS;


template<class T> inline void checkmin(T &a, T b) { if (b<a) a=b; }
template<class T> inline void checkmax(T &a, T b) { if (b>a) a=b; }
//template<class T> inline void swap(T& x , T& y){ x ^= y; y ^= x; x ^= y; }
//template<class T> inline T gcd(T a, T b) { if( a < b )swap(a, b); return b == 0 ? a : gcd(b, a % b);}
template<class T> inline T abs(T x) { return x < 0 ?  -x : x ;}
template<class T> inline T extgcd(T a, T b, T& x, T& y){
    int d = a; if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a / b) * x;
    }
    else {
        x = 1; y = 0;
    }
    return d;
}
template<class T> inline T mypow(T n, T k){ T res = 1; for(T i = 0; i < k; ++i)res *= n; return res;}
template<class T> inline T mod_pow(T x, T n, T mod){T res = 1; while( n ){if( n & 1)res = res * 1LL * x % mod; x = x * 1LL * x % mod; n >>= 1; } return res;}
template<class T> inline T add(int* b, int i, T x, int N){
    while(i <= N){
        *(b + i) += x;
        x += lowbit(x);
    }
}

template<class T> inline T getsum(int* b, int i){
    T res = 0;
    while(i > 0){
        res += *(b + i);
        i -= lowbit(i);
    }
    return res;
}

template<class T> inline void add_mod(T &a, int mod = -1) {
	if(mod == -1) mod = 1e9 + 7;
	while(a >= mod) a -= mod;
	while(a < 0) a += mod;
}
/********************************************************/

const int maxn = 1e5 + 10;
const ll mod  = 1e9 + 7;
const int inf  = 2147483647;
const int sigma_size = 26;
const ll LLMAX = 0x7fffffffffffffffLL;
const ll LLMIN = 0x8000000000000000LL;
const int INF  = 2147483647;
const int IMIN = 0x80000000;
const ll MOD   = 1000000007LL;
const double pi = acos(-1.0);

/********************************************************/
inline int pdt(int x,int y) {  ///����x * y % MOD
  int ret; __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(x),"b"(y),"c"(MOD));
  return ret;
}
//#define freopenin
//#define freopenou
ll gcd(ll a, ll b, ll *x, ll *y)
{
    ll tx, ty;
    ll g;

    if (b > a)
        return gcd(b, a, y, x);

    if (b == 0)
    {
        *x = 1;
        *y = 0;

        return a;
    }

    g = gcd(b, a % b, &tx, &ty);

    *x = ty;
    *y = tx - floor(a / b) * ty;

    return g;
}

ll binomialCoeff(int n, int k)
{
    ll C[k+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;  // nC0 is 1

    for (int i = 1; i <= n; i++)
    {
        // Compute next row of pascal triangle using
        // the previous row
        for (int j = min(i, k); j > 0; j--)
            C[j] = (C[j] + C[j-1]) % mod;
    }
    return C[k] % mod;
}

ll dp[1010][1010];
//ll inv[4000010];
//int init(){
//    inv[1] = 1;
//    for(int i = 2; i < 4000010; i ++){
//        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
//    }
//}

ll getdp(int a, int b, int k) {
	if (b >= k) return b;
	return dp[a][b];
}
bool prime[123456];
bool cnt[123456];
int sum[123456];
void init(){
    for(int i=2;i<123456;++i)prime[i]=1;
    memset(sum, 0, sizeof(sum));
    memset(cnt, 0, sizeof(cnt));
    prime[0] = prime[1] = 0;
    for(int i = 2; i < 123456; ++i){
        if(prime[i])
        for(int j = i * 2; j < 123456; j += i){
            prime[j] = 0;
        }
    }

    for(int i = 2; i < 123456; ++i){
        if(prime[i]){
        if(prime[(i + 1)/2])cnt[i]=1;
        }
    }
    for(int i = 1; i < 123456; ++i){
        if(cnt[i])sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }
//    cout<<cnt[3]<<" "<<cnt[5]<<endl;
//    for(int i=1;i<12345;++i)cout<<prime[i]<<" ";
}
int main(){
        ios_base::sync_with_stdio(0);///g++�������
        #ifdef cc
        int __size__ = 256 << 20; // 256MB  G++
        char *__p__ = (char*)malloc(__size__) + __size__;
        __asm__("movl %0, %%esp\n" :: "r"(__p__));
        #endif // cc
        #ifdef  freopenin
            freopen("input.txt","r",stdin);
        #endif // freopenin

        #ifdef freopenout
            freopen("out.txt","r",stdout);
        #endif // freopenout
        int q, l, r;
        init();
        cin>>q;
        while(q--){
            cin>>l>>r;
            cout<<sum[r]-sum[l-1]<<endl;
        }
        return 0;
}


Measured memory_bytes: 1408