#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


#define MAXN 150000			// total # of prime numbers
#define MAXP 1001002		// highest number to test prime

int prime[MAXN];		// prime numbers: 2, 3, 5 ...
int lp[MAXP];		// lp[n] = n if n is prime; otherwise smallest prime factor of the number
int phi[MAXP];			// phii function

class prime_class {
public:
	long top;

	prime_class() {			// generate all prime under MAXP
		int i, i2, j;

		top = 0;
		lp[0] = 0;
		lp[1] = 1;
		for (i = 2; i < MAXP; i++) lp[i] = 0;

		top = 0;
		for (i = 2; i < MAXP; ++i) {
			if (lp[i] == 0) {
				lp[i] = i;
				prime[top++] = i;
			}
			for (j = 0; (j < top) && (prime[j] <= lp[i]) && (i * prime[j] < MAXP); ++j)
				lp[i * prime[j]] = prime[j];
		}
	}

	bool isprime(int key)
	{
		if (key < MAXP)	return (lp[key] == key) && (key >= 2);
		else {
			int i;
			for (i = 0; (i < top) && (prime[i] * prime[i] <= key); i++)
				if (key % prime[i] == 0) return false;
			return true;
		}
	}

	unordered_map<int, int> factorize(int key) {
		unordered_map<int, int> ans;

		while (lp[key] != key) {
			ans[lp[key]]++;
			key /= lp[key];
		}
		if (key > 1) ans[key]++;

		return ans;
	}

	int get_phi(int key) {	// calculate Euler's totient function, also known as phi-function
		int ans = key, last = 0;

		while (lp[key] != key) {
			if (lp[key] != last) {
				last = lp[key];
				ans -= ans / last;
			}
			key /= lp[key];
		}
		if ((key > 1) && (key != last)) ans -= ans / key;

		return ans;
	}

	void calc_all_phi(int n) {
		int i, j, k;
		for (int i = 1; i < n; i++) phi[i] = i;
		for (int i = 2; i < n; i++) {
			if (phi[i] == i) {
				for (int j = i; j < n; j += i) {
					phi[j] /= i;
					phi[j] *= i - 1;
				}
			}
		}
	}

	vector<pair<long long, long long>> factorize_full(long long key) {		// can be used to factorize numbers >= MAXP
		vector<pair<long long, long long>> ans;

		long i, ct;

		for (i = 0; (i < top) && (prime[i] <= key); i++)
			if (key % prime[i] == 0) {
				ct = 0;
				while (key % prime[i] == 0) {
					ct++;
					key /= prime[i];
				}
				ans.push_back({ prime[i], ct });
			}
		if (key > 1) {
			ans.push_back({ key, 1 });
		}
		return ans;
	}

	void generate_divisors(int step, int v, vector<pair<int, int>>& fp, vector<int>& ans) {
		if (step < fp.size()) {
			generate_divisors(step + 1, v, fp, ans);
			for (int i = 1; i <= fp[step].second; i++) {
				v *= fp[step].first;
				generate_divisors(step + 1, v, fp, ans);
			}
		}
		else ans.push_back(v);
	}

	void generate_divisors_full(long long step, long long v, vector<pair<long long, long long>>& fp, vector<long long>& ans) {
		if (step < fp.size()) {
			generate_divisors_full(step + 1, v, fp, ans);
			for (int i = 1; i <= fp[step].second; i++) {
				v *= fp[step].first;
				generate_divisors_full(step + 1, v, fp, ans);
			}
		}
		else ans.push_back(v);
	}

	vector<int> get_divisors(int key) {
		unordered_map<int, int> f = factorize(key);
		int n = f.size();
		vector<pair<int, int>> fp;
		for (auto p : f) fp.push_back(p);
		vector<int> ans;
		generate_divisors(0, 1, fp, ans);
		return ans;
	}

	vector<long long> get_divisors_full(long long key) {
		vector<pair<long long, long long>> f = factorize_full(key);
		int n = f.size();
		vector<pair<long long, long long>> fp;
		for (auto p : f) fp.push_back(p);
		vector<long long> ans;
		generate_divisors_full(0, 1, fp, ans);
		return ans;
	}


};

#define MAXN 100010

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	prime_class pr;
	vector<int> c(MAXN);
	int i, j, k, t, l, r;
	c[0] = 0;
	for (i = 1; i < MAXN; i++) {
		c[i] = c[i - 1];
		if ((i % 2 == 1) && pr.isprime(i) && pr.isprime((i + 1) / 2)) c[i]++;
	}

	cin >> t;
	while (t--) {
		cin >> l >> r;
		cout << c[r] - c[l - 1] << "\n";
	}

	return 0;
}



Measured memory_bytes: 7168