#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}

template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}

template<typename Value> class CumulativeSum1D {
private:
  struct RangeValue {
    int i, j;
    Value v;
    RangeValue(int i, int j, Value v) : i(i), j(j), v(v) {}
  };

  vector<Value> val;
  vector<RangeValue> rangeValue;

public:
  CumulativeSum1D(int n) : val(n + 2) {}

  CumulativeSum1D(size_t n) : val(n + 2) {}

  template<typename T> CumulativeSum1D(T v) : val(v.size() + 2) {
    partial_sum(v.begin(), v.end(), val.begin() + 1);
  }

  void add(int i, Value v) {
    add(i, i + 1, v);
  }

  void add(int i, int j, Value v) {
    rangeValue.emplace_back(i, j, v);
  }

  // [i,j)
  Value sum(int i, int j) {
    if (!rangeValue.empty()) {
      adjacent_difference(val.begin(), val.end(), val.begin());
      adjacent_difference(val.begin(), val.end(), val.begin());
      for (const auto& v : rangeValue) {
        val[v.i + 1] += v.v;
        val[v.j + 1] -= v.v;
      }
      partial_sum(val.begin(), val.end(), val.begin());
      partial_sum(val.begin(), val.end(), val.begin());
      rangeValue.clear();
    }
    return val[j] - val[i];
  }

  Value value(int i) {
    return sum(i, i + 1);
  }

  Value max() {
    auto res = numeric_limits<Value>::min();
    for (int i = 0; i < int(val.size()) - 2; ++i) chmax(res, value(i));
    return res;
  }
};

class Prime {
private:
  vector<int64_t> div;
  
public:
  Prime(int64_t n = 0) {
    for (int64_t i = 0; i <= n; ++i) div.emplace_back(i);
    for (int64_t i = 2; i <= n / i; ++i) if (div[i] == i) {
      for (int64_t j = i * i; j <= n; j += i) div[j] = i;
    }
  }
  
  bool isPrime(int64_t n) const {
    if (n <= 1) return false;
    if (n < int64_t(div.size())) return div[n] == n;
    for (int64_t i = 2; i <= n / i; ++i) if (n % i == 0) return false;
    return true;
  }
  
  vector<int64_t> factor(int64_t n) const {
    vector<int64_t> res;
    for (int64_t i = 2; i <= n / i && n >= int64_t(div.size()); ++i) {
      while (n % i == 0) {
        res.emplace_back(i);
        n /= i;
      }
    }
    if (n >= max(int(div.size()), 2)) {
      res.emplace_back(n);
    } else {
      while (n > 1) {
        res.emplace_back(div[n]);
        n /= div[n];
      }
    }
    sort(res.begin(), res.end());
    return res;
  }
  
  vector<int64_t> primeFactor(int64_t n) const {
    vector<int64_t> res;
    for (int64_t i = 2; i <= n / i && n >= int64_t(div.size()); ++i) {
      if (n % i) continue;
      res.emplace_back(i);
      while (n % i == 0) n /= i;
    }
    if (n >= max(int(div.size()), 2)) {
      res.emplace_back(n);
    } else {
      while (n > 1) {
        int64_t d = div[n];
        res.emplace_back(d);
        while (n % d == 0) n /= d;
      }
    }
    sort(res.begin(), res.end());
    return res;
  }

  vector<int64_t> divisor(int64_t n) const {
    vector<int64_t> res;
    for (int64_t i = 1; i <= n / i; ++i) {
      if (n % i == 0) {
        res.emplace_back(i);
        if (i != n / i) res.emplace_back(n / i);
      }
    }
    sort(res.begin(), res.end());
    return res;
  }

  vector<int64_t> primes(int64_t n) const {
    vector<int64_t> res;
    for (int64_t i = 2; i <= n; ++i) {
      if (isPrime(i)) res.emplace_back(i);
    }
    return res;
  }
};

int main() {
  Prime prime(100001);
  CumulativeSum1D<int> sum(100001);
  for (int i = 1; i < 100000; i += 2) {
    if (prime.isPrime(i) && prime.isPrime((i + 1) / 2)) sum.add(i, 1);
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    cout << sum.sum(l, r + 1) << endl;
  }
}



Measured memory_bytes: 1908