#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a[100001], b[100001], c[100001], i, j, n, s, e;
	for (i=2; i<=100000; i++) a[i]=1;
	for (i=2; i<=int(sqrt(100000)); i++)
		if (a[i]==1)
			for (j=i*2; j<=100000; j+=i) a[j]=0;
	b[1]=0;
	b[2]=0;
	for (i=3; i<=100000; i++)
		if (a[i]==1&&a[(i+1)/2]==1) b[i]=1;
	c[1]=0;
	c[2]=0;
	for (i=3; i<=100000; i++) c[i]=c[i-1]+b[i];
	cin >> n;
	for (i=1; i<=n; i++)
	{
		cin >> s >> e;
		cout << c[e]-c[s-1] << endl;
	}
	return 0;
}