#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], * di = dn;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[3];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

int like[500001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();

	int like2017[672] = {2,3,7,19,31,37,79,97,139,157,199,211,229,271,307,331,337,367,379,439,499,547,577,601,607,619,661,691,727,811,829,877,937,967,997,1009,1069,1171,1237,1279,1297,1399,1429,1459,1531,1609,1627,1657,1759,1867,2011,2029,2089,2131,2137,2179,2221,2281,2311,2467,2539,2551,2557,2617,2707,2719,2791,2851,3019,3037,3061,3067,3109,3169,3181,3187,3319,3331,3391,3499,3529,3607,3697,3709,3739,3769,3877,3967,4027,4051,4111,4159,4177,4231,4261,4339,4357,4447,4507,4567,4591,4621,4639,4801,4831,4861,4909,4951,4987,5167,5179,5227,5419,5431,5479,5557,5581,5659,5749,5839,5851,6037,6079,6121,6151,6211,6217,6229,6271,6277,6301,6361,6379,6421,6427,6547,6691,6709,6841,6961,6967,7219,7297,7369,7411,7507,7537,7561,7621,7639,7681,7687,7867,7951,8017,8167,8191,8209,8287,8317,8329,8461,8521,8527,8539,8629,8647,8689,8941,9007,9049,9067,9091,9109,9127,9151,9157,9199,9241,9277,9319,9397,9619,9721,9739,9859,9901,9907,9931,10177,10267,10321,10429,10501,10531,10597,10639,10657,10789,10831,10837,10909,11047,11251,11287,11311,11497,11527,11587,11779,11839,11887,11959,12049,12211,12241,12391,12421,12517,12577,12619,12781,12829,12967,13009,13147,13159,13219,13249,13411,13417,13441,13477,13537,13627,13669,13681,13729,13999,14029,14149,14197,14407,14419,14461,14551,14737,14821,15091,15121,15259,15277,15289,15319,15331,15349,15391,15427,15541,15619,15661,15667,15679,15739,15787,15937,15991,16087,16189,16249,16267,16417,16519,16651,16729,16747,16879,16981,17029,17107,17137,17191,17257,17449,17491,17659,17761,17839,17989,18049,18121,18217,18229,18397,18439,18451,18457,18637,18661,18679,18787,18859,18979,19141,19231,19417,19477,19489,19609,19687,19699,19867,20047,20089,20107,20347,20407,20509,20611,20641,20707,20809,20947,21031,21169,21187,21397,21481,21559,21589,21601,21661,21787,21799,21817,21859,22027,22051,22111,22129,22147,22447,22531,22669,22717,22741,22777,22807,22921,23011,23071,23131,23431,23497,23509,23581,23677,23761,23767,23827,23857,23869,23899,23929,24061,24097,24169,24337,24379,24391,24517,24631,24697,24709,24799,24841,24979,25111,25171,25189,25411,25447,25579,25609,25621,25741,25759,25819,26029,26041,26119,26161,26227,26251,26407,26431,26479,26539,26557,26641,26701,26959,27061,27067,27091,27109,27211,27259,27271,27337,27361,27487,27529,27691,27751,27817,27919,27961,27967,28027,28051,28057,28099,28201,28219,28351,28387,28411,28429,28447,28537,28549,28597,28621,28687,28729,28927,29077,29209,29221,29269,29287,29347,29527,29599,29611,29641,29671,29917,30109,30169,30187,30319,30367,30469,30529,30577,30631,30649,30781,30829,30841,30859,30931,31069,31237,31249,31267,31327,31387,31657,31699,31771,31849,31891,31957,32077,32119,32191,32257,32359,32587,32647,32707,32719,32749,32779,32839,32941,33151,33181,33301,33349,33427,33487,33529,33577,33637,33739,33769,33871,33889,33967,33997,34057,34141,34261,34369,34501,34537,34729,34747,34849,34939,35059,35089,35149,35251,35311,35461,35491,35617,35671,35677,35797,35911,36037,36241,36307,36451,36469,36571,36709,36739,36781,36847,37039,37159,37189,37357,37507,37567,37591,37861,37897,37957,38167,38281,38299,38377,38569,38821,39079,39097,39139,39439,39451,39667,39679,39769,39829,39847,39901,39937,40039,40087,40111,40237,40351,40357,40459,40507,40591,40759,40819,40927,41011,41077,41131,41281,41491,41539,41611,41617,41719,41809,41851,41887,42061,42157,42337,42349,42397,42457,42649,42667,42727,42859,42967,43177,43207,43591,43627,43669,43711,43717,43759,43777,43987,44059,44089,44119,44131,44257,44371,44449,44497,44647,44917,44959,45061,45541,45691,45697,45757,45979,46021,46279,46381,46411,46447,46471,46549,46567,46747,46819,46957,47017,47059,47137,47161,47221,47287,47389,47419,47497,47629,47659,47701,47791,47809,47857,47869,48049,48079,48091,48247,48259,48487,48541,48589,48751,48781,48889,48907,49009,49369,49477,49639,49789,49831,49939};

	rep(i, 672) like[like2017[i]] = 1;
	rep(i, 500000) like[i + 1] += like[i];

	rep(i, N) {
		int l = getint() >> 1, r = getint() >> 1;
		putint(like[r + 1] - like[l]);
	}
	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

Measured memory_bytes: 4736