import std.string;
import std.stdio;

const(bool)[] sieve(size_t length) {
	auto primes = new bool[length];
	primes[2..$] = true;

	foreach (size_t i, e;primes) {
		if (!e) {
			continue;
		}
		for (auto j = i * 2;j < primes.length;j += i) {
			primes[j] = false;
		}
	}

	return primes;
}

const(bool)[] like2017(size_t length) {
	auto primes = sieve(length);
	auto like2017s = new bool[length];

	for (auto i = 3;i < like2017s.length;i += 2) {
		if (primes[i] && primes[(i + 1) / 2]) {
			like2017s[i] = true;
		}
	}

	return like2017s;
}

const(int)[] totalLike2017s(size_t length) {
	auto l = like2017(length);
	auto totals = new int[length + 1];

	foreach (size_t i, e;l) {
		if (e) {
			totals[i + 1] = totals[i] + 1;
		} else {
			totals[i + 1] = totals[i];
		}
	}

	return totals;
}

void main() {
	enum Max = 100000;

	int n;
	readf(" %s", &n);

	static totals = totalLike2017s(Max);

	foreach (i;0..n) {
		int l, r;
		readf(" %s %s", &l, &r);
		writeln(totals[r + 1] - totals[l]);
	}
}
