// Slower C++ solution:
/**

*　　　　　　　　┏┓　　 　┏┓

* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

* 　　　　　　　┃　　　　　　　┃ 　

* 　　　　　　　┃　　　━　　 　┃

* 　　　　　　　┃　＞　　　＜　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┃...　⌒　... 　┃

* 　　　　　　　┃　　　　　　　┃

* 　　　　　　　┗━┓　　　┏━┛

* 　　　　　　　　　┃　　　┃　　　　　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┃  　　　　　　

* 　　　　　　　　　┃　　　┃

* 　　　　　　　　　┃　　　┃　　　　　　　　　　　

* 　　　　　　　　　┃　　　┗━━━┓

* 　　　　　　　　　┃　　　　　　　┣┓

* 　　　　　　　　　┃　　　　　　　┏┛

* 　　　　　　　　　┗┓┓┏━┳┓┏┛

* 　　　　　　　　　　┃┫┫　┃┫┫

* 　　　　　　　　　　┗┻┛　┗┻┛

*/

#include<iostream>  

#include<cstdio>  

#include<fstream>  

#include<iomanip>

#include<algorithm>  

#include<cmath>  

#include<deque>  

#include<vector>

#include<bitset>

#include<queue>  

#include<string>  

#include<cstring>  

#include<map>  

#include<stack>  

#include<set>

#include<cassert>

#include<functional>



#define pii pair<int, int>

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define eps 0.000000001

#define mst(a,i) memset(a,i,sizeof(a))

#define all(n) n.begin(),n.end()

#define lson(x) ((x<<1))  

#define rson(x) ((x<<1)|1) 

#define inf 0x3f3f3f3f

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;



vector<int>prime;

int isprime[maxn];



void getprimelist(int t)

{

	mst(isprime, 1);

	isprime[1] = 0;

	for (int i = 2; i <= t; ++i)

	{

		if (isprime[i])prime.push_back(i);

		for (int j = 0; j < prime.size() && prime[j] * i <= t; ++j)

		{

			isprime[prime[j] * i] = 0;

			if (i%prime[j] == 0)break;

		}

	}

}

int ok[maxn];

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0); cout.tie(0);

#ifdef DEBUG

	freopen("old_data.json", "r", stdin);

	freopen("1.out", "w", stdout);

#endif // DEBUG clang++ checker.cpp --target=i686-pc-mingw32 -o checker.exe

	int n;

	getprimelist(100000);

	for (int i = 1; i <= 100000; ++i) {

		if (isprime[i] && isprime[(i + 1) / 2])ok[i] = 1;

	}

	for (int i = 1; i <= 100000; ++i)ok[i] += ok[i - 1];

	cin >> n;

	int l, r;

	for (int i = 1; i <= n; ++i) {

		cin >> l >> r;

		cout << ok[r] - ok[l - 1] << endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2576858542140563x):
/*

                  友利奈緒ぱわーでACしてくれ！！！！！！！！！！！！

                  Charlotteまだ見てない人は見ような！！！！！！！



                  ／　 /:／　　　　　　　　　　　 　 ＼:ヽ　＼

  　　　　　　　 /　　／　　　　　　 　 　 　 　 　 　 　 ＼　　ヽ

  　　　　　＼__L 彡　　　　　　　　　　　　　　　　　　　 ヽ　　',

  　　　　　　　ﾌ /　　　/　　/　 /　　　,　　 　 　 　 ヽ　　', 　ｊ

  　　　　　　　ﾚ　　　 /　　/ 　/　 　 　 　 　 　 　 　 ', 　ヽ　j

  　　　 　 　 // 　 　 !　/_l＿/__ノ 　　{ ＼}　　　　 　 ',　　',/

  　　　　　　i ﾊ 　 　 {　从j　ﾊ　i　　　 ',　 ト-､}　 i i　 }　　jj

  　　　　　　( ﾊ　　　(　 川　ハ ﾊ　 !　 '　ﾊ　 ﾊ　j j　,' 　 八

  　　　 ＜＿,ｨ∧　　　斗芹ﾃミxハ ﾊ　 ﾚ　} /__ﾚﾚ　/ 　 ∧ ＼　ﾉ

  　　　 　 　 ∨　＼ 　ゝ　辷:ソ　　 　)　芹ﾚ心ヾレ′　/ ト--　´

  　　　＼ｰ‐'　ﾉ　　 ＼ゝ　　　　　　 　 　 ゞ:_ソ "/ 　／ 　ヽ

  　　　　 　 フ　　　　i八 " "　　　,　　　　　　　ム彡　　　　＼

  　　　　 　/　　/　　j　 ト　　　　　　 　 　 " "イト＜　 　 　 ＼＼

  　　　　 /　　/　　　j　/／ヽ､ 　 ∩　　 　 イ　{ {　　￣ フフへ ＼＼

  　　　　(　／　　　 ,/ / 　　i　＞――＜ニニニﾆ┐　 〃／: : ヽ　ヽヽ

  　　　　／　　ィT´/ /┌―　￣￣ /::: , ,)　 　 　 〃／／: : : : : :}　ヽヽ)

  　　　/ /　 ∧ヾi┌― { {￣　　　 ﾉ:::トﾟ<　 　 　 ∥//: : : : : : : : i　 ﾉ ﾉ

  . 　　( 人　 {:ヽヾi∨　∧V　　　 /:::/　､ヽ　　　 ∥/: : : : : : : : : :}　/

  　　　V　( ∧: :＼'∨　∧V　　 ﾉ:::/　 ∧ 〉＿__∥: : : : : :／: : : :ﾚ

  　　 　 　 /∧: : : : ∨　∧V┬ｲ:::ﾉ　 〈 TT　|　|{{: : : : ／: : : : : ∧　　 ﾉ

  　　　 　 (　ハ: : : : :∨'T∧Vi　i (　 　 V　!　!　{{: : ／ : : : : : : /　ｰ　ノ

  　　　　　V　ハ: : : : :∨ﾍ∧V　i ゝゝ　 i／⌒＼{／ : : : : : : : /ｰ― ´

  　　　　　 ∨　ヽ: : : : :∨ﾍ∧∨i　〉 〉 /　/二　 ): : : : : : : : :/



          (https://seesaawiki.jp/asciiart/d/Charlotte より)

*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long; using ull = unsigned long long;

// #define int ll

// #define DEBUG 42

inline void nprint(){}

template <class Head, class... Tail>

inline void nprint(Head &&head, Tail &&... tail) {

    cout << head << endl;

    nprint(move(tail)...);

}

#ifdef DEBUG

  #define eprint(...) nprint(__VA_ARGS__)

#else

  #define eprint(...) if(0==1) cout << 1 << endl;

#endif

#define Yes(a) cout << (a ? "Yes" : "No") << endl

#define YES(a) cout << (a ? "YES" : "NO") << endl

#define POSSIBLE(a) cout << (a ? "POSSIBLE" : "IMPOSSIBLE") << endl

using cmp = complex<double>;

using vb = vector<bool>; using vvb = vector<vb>;

using vi = vector<int>; using vvi = vector<vi>;

using vl = vector<ll>; using vvl = vector<vl>;

template<class T> using V = vector<T>;

template<class T> using VV = vector<V<T>>;

#define fi first

#define se second

#define maxs(x,y) (x=max(x,y))

#define mins(x,y) (x=min(x,y))

using pii = pair<int,int>; using pll = pair<ll,ll>;

#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)

#define REP(i,n) FOR(i,0,n)

#define FORS(i,a,b) FOR(i,a,b+1)

#define REPS(i,n) REP(i,n+1)

#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)

#define RREP(i,n) RFOR(i,0,n)

#define RREPS(i,n) RREP(i,n+1)

#define RFORS(i,a,b) RFOR(i,a,b+1)

#define ALL(obj) (obj).begin(), (obj).end()

#define RALL(obj) (obj).rbegin(), (obj).rend()

#define PERM(c) sort(ALL(c)); for(bool cp = true;cp;cp = next_permutation(ALL(c)))

#define eb(val) emplace_back(val)

constexpr double PI = acos(-1), EPS = 1e-10;

constexpr ll MOD = 1E9+7;

constexpr int dx[] = {1,0,-1,0}; constexpr int dy[] = {0,1,0,-1};

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p){

  return s << "(" << p.first << ", " << p.second << ")";

}

template<class T> istream& operator>>(istream &is,vector<T> &st){

  for(size_t i=0;i<st.size();++i) is >> st[i];

  return is;

}

template<class T> istream& operator>>(istream &is,vector<vector<T>> &st){

  for(size_t i=0;i<st.size();++i) is >> st[i];

  return is;

}

template<class T> ostream& operator<<(ostream &os, const vector<T> &st){

  for(size_t i=0;i<st.size();++i){

    if(i==st.size()-1) os << st[i];

    else os << st[i] << " ";

  }

  return os;

}

template<class T> ostream& operator<<(ostream &os, const vector<vector<T>> &st){

  for(size_t i=0;i<st.size();++i){

    os << st[i];

    if(i!=st.size()-1) os << endl;

  }

  return os;

}

pair<vl,vb> eratosthenes_sieve(ll n){

  vb is_prime(n+1,true);

  vl prime;

  is_prime[0] = false;

  is_prime[1] = false;

  FOR(i,2,sqrt(n)+1){

    if(!is_prime[i]) continue;

    for(ll j=2*i;j<=n;j+=i) is_prime[j] = false;

    prime.eb(i);

  }

  FOR(i,sqrt(n)+1,n+1){

    if(is_prime[i])prime.eb(i);

  }

  return {prime,is_prime};

}

signed main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  cout << fixed << setprecision(10);

  int q;

  cin >> q;

  auto lst = eratosthenes_sieve(100005).se;

  vi sum(100005,0);

  FOR(i,1,100001){

    if(i%2&&lst[i]&&lst[(i+1)/2]) sum[i] = sum[i-1]+1;

    else sum[i] = sum[i-1];

  }

  REP(i,q){

    int l,r;

    cin >> l >> r;

    cout << sum[r] - sum[l-1] << endl;

  }

}