#include<bits/stdc++.h>
using namespace std;
bool f[100001];
int C[100002];
int N, L, R;
int main() {
  cin>>N;
	for (int i = 2; i <= 100000; i++)if (!f[i])for (int j = i + i; j <= 100000; j += i) f[j] = true;
	for (int i = 3; i <= 100000; i+=2) {
		if (!f[i] && !f[(i + 1) / 2]) C[i]++;
	}
	for (int i = 3; i <= 100000; i++) C[i] += C[i - 1];
	while (N--) {
		cin >> L >> R;
		cout << C[R] - C[L - 1] << endl;
	}
}