// Original C++ solution (slower):
#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

template <class T>

inline bool chmax(T &a, T b) {

  if (a < b) {

    a = b;

    return 1;

  }

  return 0;

}



typedef long long ll;

ll MOD = 1000000007;



// a^p

// 2^3 = 2 * 2^2

// 2^2 = 2 * (2^1)

// 2^1 = 2

ll modpow(ll a, ll p, ll mod) {

  if (p == 0) return 1;



  if (p % 2 == 0) {

    ll half = modpow(a, p / 2, mod) % mod;

    return half * half % mod;

  } else {

    return a * modpow(a, p - 1, mod) % mod;

  }

}



// nCa を求める

ll modCombination(ll n, ll a, ll mod) {

  if (n - a < a) {

    return modCombination(n, n - a, mod);

  }



  ll denominator = 1;  // 分母

  ll numerator = 1;    // 分子



  for (ll i = 0; i < a; i++) {

    denominator *= a - i;

    numerator *= n - i;

    denominator %= mod;

    numerator %= mod;

  }



  return numerator * modpow(denominator, mod - 2, mod) % mod;

}



class UnionFind {

 private:

  vector<ll> parents;



 public:

  UnionFind(ll n) : parents(n, -1) {}



  bool issame(ll x, ll y) { return root(x) == root(y); }



  bool merge(ll x, ll y) {

    if (issame(x, y)) return false;



    ll rx = root(x);

    ll ry = root(y);

    if (parents[rx] > parents[ry]) swap(rx, ry);

    // サイズ情報を更新

    parents[rx] += parents[ry];

    // yの親を更新

    parents[ry] = rx;



    return true;

  }



  ll size(ll x) { return -parents[root(x)]; }



 private:

  ll root(ll x) {

    if (parents[x] < 0) return x;

    // 根の親の値に木の(-)サイズの情報を入れる

    return parents[x] = root(parents[x]);

  }

};



int main() {

  ll Q;

  cin >> Q;

  vector<ll> l(Q);

  vector<ll> r(Q);

  for (ll i = 0; i < Q; i++) {

    cin >> l[i] >> r[i];

  }



  ll MAX = 100001;

  vector<bool> isprime(MAX, true);

  isprime[0] = false;

  isprime[1] = false;

  for (ll i = 2; i <= MAX; i++) {

    if (!isprime[i]) continue;



    for (ll j = i * 2; j <= MAX; j += i) {

      isprime[j] = false;

    }

  }



  vector<ll> a(MAX, 0);

  for (ll i = 0; i < MAX; i++) {

    if (isprime[i] && isprime[(i + 1) / 2]) {

      a[i] = 1;

    }

  }



  // [0, i)

  // a[0] ~ a[i] までの総和

  vector<ll> sum(MAX + 1, 0);

  sum[0] = 0;

  for (ll i = 0; i < MAX; i++) {

    sum[i + 1] = sum[i] + a[i];

  }



  for (ll i = 0; i < Q; i++) {

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

  }



  return 0;

}


// Optimized solution to the same problem (faster):
#include <string.h>

#include <algorithm>

#include <bitset>

#include <iostream>

#include <sstream>

#include <vector>

using namespace std;

template <class T>

inline bool chmax(T &a, T b) {

  if (a < b) {

    a = b;

    return 1;

  }

  return 0;

}

template <typename T>

inline string toString(const T &a) {

  ostringstream oss;

  oss << a;

  return oss.str();

};



typedef long long ll;



int main() {

  ll Q;

  cin >> Q;

  vector<ll> L(Q);

  vector<ll> R(Q);

  for (ll i = 0; i < Q; i++) {

    cin >> L[i] >> R[i];

  }



  ll N = 100000;

  // ll N = 10;



  vector<bool> isPrime(N + 1, true);

  // 0と1は素数ではない

  isPrime[0] = false;

  isPrime[1] = false;

  // 2からスタート

  for (ll i = 2; i <= N; i++) {

    if (isPrime[i] == false) continue;

    // 2は素数

    // 4, 6, 8, 10, ... は素数ではない

    // 3は素数

    // 6, 9, 12, 15, ... は素数ではない

    for (ll j = i * 2; j <= N; j += i) {

      isPrime[j] = false;

    }

  }



  vector<ll> sum(N + 2, 0);

  for (ll i = 0; i < N + 1; i++) {

    if (isPrime[i] && isPrime[(i + 1) / 2]) {

      sum[i + 1] = sum[i] + 1;

    } else {

      sum[i + 1] = sum[i];

    }

  }



  // for (auto s : sum) {

  //   cout << s << endl;

  // }



  for (ll i = 0; i < Q; i++) {

    ll l = L[i];

    ll r = R[i];



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

  }



  return 0;

}


// Fastest known solution for this problem: