// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for (ll i = 0; i < n; ++i)

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

#define SUM(x) std::accumulate(ALL(x), 0LL)

#define MIN(v) *std::min_element(v.begin(), v.end())

#define MAX(v) *std::max_element(v.begin(), v.end())

#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)

using namespace std;



typedef long long ll;



template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INF = 1e9;

const long long INFL = 1LL<<60;



vector<int> createEratos(int n)

{

  vector<int> isprime(n+1, 1);

  isprime[0] = 0;

  isprime[1] = 0;



  for (int i = 2; i * i <= n; i++) {

    if (isprime[i]) {

      int j = i + i;

      while (j <= n) {

        isprime[j] = 0;

        j = j + i;

      }

    }

  }

  return isprime;

}



vector<int> eratos;



bool like2017(const int& n) {

  return (eratos[n] == 1 && eratos[(n+1)/2] == 1) ? true : false;

}



int main() {

  int q;

  cin >> q;



  eratos = createEratos(1e+5);



  // 1. 1 ~ 10^5 までの2017に似た数の累積和を求める

  ll sum = 0;

  vector<ll> values(1e5 + 1, 0);

  for (int i = 3; i <= 1e5; i++) {

    if (like2017(i)) {

      sum++;

    }

    values[i] = sum;

  }



  rep(i, q) {

    int l, r;

    cin >> l >> r;

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

  }



  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.130026460281848x):
#include <bits/stdc++.h>

#define rep(i,n) for (ll i = 0; i < n; ++i)

#define sz(x) int(x.size())

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

#define SUM(x) std::accumulate(ALL(x), 0LL)

#define MIN(v) *std::min_element(v.begin(), v.end())

#define MAX(v) *std::max_element(v.begin(), v.end())

#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)

using namespace std;



using ll = int64_t;



template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = 1001001001;

const ll INFL = (1LL<<60);

const double eps = (1e-9);



using P = pair<int, int>;



struct Sieve {

  int n;

  vector<int> f, primes;

  // 1~n までの素数を求める

  Sieve(int n=1):n(n), f(n+1) {

    f[0] = f[1] = -1;

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

      if (f[i]) continue;

      primes.push_back(i);

      f[i] = i;

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

        if (!f[j]) f[j] = i;

      }

    }

  }

  bool isPrime(int x) { return f[x] == x;}

  vector<int> factorList(int x) {

    vector<int> res;

    while (x != 1) {

      res.push_back(f[x]);

      x /= f[x];

    }

    return res;

  }

  // 素因数分解の結果を返す

  vector<P> factor(int x) {

    vector<int> fl = factorList(x);

    if (fl.size() == 0) return {};

    vector<P> res(1, P(fl[0], 0));

    for (int p : fl) {

      if (res.back().first == p) {

        res.back().second++;

      } else {

        res.emplace_back(p, 1);

      }

    }

    return res;

  }

};



int main() {

  cin.tie(0);

  ios::sync_with_stdio(false);



  int q;

  cin >> q;



  Sieve sieve(1e5);



  vector<int> w(100001, 0);

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

    w[i] = w[i-1];

    if (i % 2 == 0) continue;



    if (sieve.isPrime(i) && sieve.isPrime((i+1) / 2)) {

      w[i] += 1;

    }

  }



  rep(i, q) {

    int l, r;

    cin >> l >> r;

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

  }



  return 0;

}