#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>

#define int ll; // ＾o＾

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define REPIR(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define TOSTRING(x) (#x)

using  ll = long long;
using PAIR = std::pair<ll, ll>;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
// using VI = std::vector<int>;
// using VVI = std::vector<std::vector<int>>;
using VVL = std::vector<std::vector<ll>>;

using std::cout;
// using std::endl;
#define endl '\n'
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::multiset;
using std::bitset;

constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
constexpr ll INF = 1LL << 60;

template<typename S, typename T>
std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template<typename S>
inline void dump(const S& x) { std::cout << TOSTRING(x) << ":" << x << endl; }

template<typename S>
inline void print(const S& x) { std::cout << x << endl; }

struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; };

//=============================================================================================

// ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// ll pow(ll a, ll b) { ll ans = 1; while (b > 0) { if (b % 2 == 1) { ans *= a; ans %= MOD; }b /= 2; a *= a; a %= MOD; }return ans; }
// ll comb(ll a, ll b) { static constexpr ll size = 1e6; static VL fac(size); static VL finv(size); static VL inv(size); static ll n = 0; if (n > a) { return fac[a] * (finv[b] * finv[a - b] % MOD) % MOD; }fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; FOR(i, 2, a + 1) { inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; fac[i] = fac[i - 1] * (ll)i%MOD; finv[i] = finv[i - 1] * inv[i] % MOD; }n = a + 1; return comb(a, b); }
// multiset<ll> prime_decomposition(ll n) { ll i = 2; multiset<ll> table{}; while (i * i <= n) { while (n % i == 0) { n /= i;	table.emplace(i); }++i; }if (n > 1) { table.emplace(n); return table; }return table; }
vector<bool> eratosthenes(ll n) { vector<bool> lst(n + 1, true); lst[0] = lst[1] = false; FOR(i, 2, n / 2 + 1) { lst[i * 2] = false; }for (ll i = 3; i <= n; i += 2) { if (lst[i] == false) { continue; }FOR(j, 2, n / i + 1) { lst[i*j] = false; } }return lst; }

//==============================================================================================

signed main() {
	ll n;
	cin >> n;
	auto lst = eratosthenes(1e5 + 1);

	vector<bool> okLst(1e5 + 1, false);
	FOR(i, 1, 1e5 / 2 + 1) {
		if (lst[i] & lst[i * 2 - 1]) { okLst[i * 2 - 1] = true; }
	}

	VL sumLst(1e5 + 2);
	REP(i, 1e5 + 1) {
		sumLst[i + 1] = sumLst[i] + okLst[i];
	}

	REP(nn, n) {
		ll l, r;
		cin >> l >> r;

		print(sumLst[r + 1] - sumLst[l]);
	}
}


Measured memory_bytes: 1408