#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 100;

vector<int> vec;
int cnt[N];
bool p[N];
int q;

int main() {
    memset(p, true, sizeof p);
    for (int i = 2; i < N; i++)
	if (p[i])
	    for (int j = 2 * i; j < N; j += i)
		p[j] = false;
    for (int i = 3; i < N; i += 2)
	if (p[i] && p[(i + 1) / 2])
	    cnt[i]++;
    for (int i = 1; i < N; i++)
	cnt[i] += cnt[i - 1];
    cin >> q;
    while (q--) {
	int l, r;
	cin >> l >> r;
	cout << cnt[r] - cnt[l - 1] << '\n';
    }
}