#include <bits/stdc++.h>

typedef int64_t ll;
typedef double dbl;

using namespace std;

const int N = 1 + (int) 1e5, M = (int) 1e6, Inf = INT_MAX - 100;
int n, m, k;

array<int, 673> good;

void magic()
{
    good[0] = 3;
    good[1] = 5;
    good[2] = 13;
    good[3] = 37;
    good[4] = 61;
    good[5] = 73;
    good[6] = 157;
    good[7] = 193;
    good[8] = 277;
    good[9] = 313;
    good[10] = 397;
    good[11] = 421;
    good[12] = 457;
    good[13] = 541;
    good[14] = 613;
    good[15] = 661;
    good[16] = 673;
    good[17] = 733;
    good[18] = 757;
    good[19] = 877;
    good[20] = 997;
    good[21] = 1093;
    good[22] = 1153;
    good[23] = 1201;
    good[24] = 1213;
    good[25] = 1237;
    good[26] = 1321;
    good[27] = 1381;
    good[28] = 1453;
    good[29] = 1621;
    good[30] = 1657;
    good[31] = 1753;
    good[32] = 1873;
    good[33] = 1933;
    good[34] = 1993;
    good[35] = 2017;
    good[36] = 2137;
    good[37] = 2341;
    good[38] = 2473;
    good[39] = 2557;
    good[40] = 2593;
    good[41] = 2797;
    good[42] = 2857;
    good[43] = 2917;
    good[44] = 3061;
    good[45] = 3217;
    good[46] = 3253;
    good[47] = 3313;
    good[48] = 3517;
    good[49] = 3733;
    good[50] = 4021;
    good[51] = 4057;
    good[52] = 4177;
    good[53] = 4261;
    good[54] = 4273;
    good[55] = 4357;
    good[56] = 4441;
    good[57] = 4561;
    good[58] = 4621;
    good[59] = 4933;
    good[60] = 5077;
    good[61] = 5101;
    good[62] = 5113;
    good[63] = 5233;
    good[64] = 5413;
    good[65] = 5437;
    good[66] = 5581;
    good[67] = 5701;
    good[68] = 6037;
    good[69] = 6073;
    good[70] = 6121;
    good[71] = 6133;
    good[72] = 6217;
    good[73] = 6337;
    good[74] = 6361;
    good[75] = 6373;
    good[76] = 6637;
    good[77] = 6661;
    good[78] = 6781;
    good[79] = 6997;
    good[80] = 7057;
    good[81] = 7213;
    good[82] = 7393;
    good[83] = 7417;
    good[84] = 7477;
    good[85] = 7537;
    good[86] = 7753;
    good[87] = 7933;
    good[88] = 8053;
    good[89] = 8101;
    good[90] = 8221;
    good[91] = 8317;
    good[92] = 8353;
    good[93] = 8461;
    good[94] = 8521;
    good[95] = 8677;
    good[96] = 8713;
    good[97] = 8893;
    good[98] = 9013;
    good[99] = 9133;
    good[100] = 9181;
    good[101] = 9241;
    good[102] = 9277;
    good[103] = 9601;
    good[104] = 9661;
    good[105] = 9721;
    good[106] = 9817;
    good[107] = 9901;
    good[108] = 9973;
    good[109] = 10333;
    good[110] = 10357;
    good[111] = 10453;
    good[112] = 10837;
    good[113] = 10861;
    good[114] = 10957;
    good[115] = 11113;
    good[116] = 11161;
    good[117] = 11317;
    good[118] = 11497;
    good[119] = 11677;
    good[120] = 11701;
    good[121] = 12073;
    good[122] = 12157;
    good[123] = 12241;
    good[124] = 12301;
    good[125] = 12421;
    good[126] = 12433;
    good[127] = 12457;
    good[128] = 12541;
    good[129] = 12553;
    good[130] = 12601;
    good[131] = 12721;
    good[132] = 12757;
    good[133] = 12841;
    good[134] = 12853;
    good[135] = 13093;
    good[136] = 13381;
    good[137] = 13417;
    good[138] = 13681;
    good[139] = 13921;
    good[140] = 13933;
    good[141] = 14437;
    good[142] = 14593;
    good[143] = 14737;
    good[144] = 14821;
    good[145] = 15013;
    good[146] = 15073;
    good[147] = 15121;
    good[148] = 15241;
    good[149] = 15277;
    good[150] = 15361;
    good[151] = 15373;
    good[152] = 15733;
    good[153] = 15901;
    good[154] = 16033;
    good[155] = 16333;
    good[156] = 16381;
    good[157] = 16417;
    good[158] = 16573;
    good[159] = 16633;
    good[160] = 16657;
    good[161] = 16921;
    good[162] = 17041;
    good[163] = 17053;
    good[164] = 17077;
    good[165] = 17257;
    good[166] = 17293;
    good[167] = 17377;
    good[168] = 17881;
    good[169] = 18013;
    good[170] = 18097;
    good[171] = 18133;
    good[172] = 18181;
    good[173] = 18217;
    good[174] = 18253;
    good[175] = 18301;
    good[176] = 18313;
    good[177] = 18397;
    good[178] = 18481;
    good[179] = 18553;
    good[180] = 18637;
    good[181] = 18793;
    good[182] = 19237;
    good[183] = 19441;
    good[184] = 19477;
    good[185] = 19717;
    good[186] = 19801;
    good[187] = 19813;
    good[188] = 19861;
    good[189] = 20353;
    good[190] = 20533;
    good[191] = 20641;
    good[192] = 20857;
    good[193] = 21001;
    good[194] = 21061;
    good[195] = 21193;
    good[196] = 21277;
    good[197] = 21313;
    good[198] = 21577;
    good[199] = 21661;
    good[200] = 21673;
    good[201] = 21817;
    good[202] = 22093;
    good[203] = 22501;
    good[204] = 22573;
    good[205] = 22621;
    good[206] = 22993;
    good[207] = 23053;
    good[208] = 23173;
    good[209] = 23557;
    good[210] = 23677;
    good[211] = 23773;
    good[212] = 23917;
    good[213] = 24097;
    good[214] = 24421;
    good[215] = 24481;
    good[216] = 24781;
    good[217] = 24841;
    good[218] = 25033;
    good[219] = 25153;
    good[220] = 25237;
    good[221] = 25561;
    good[222] = 25657;
    good[223] = 25933;
    good[224] = 26017;
    good[225] = 26293;
    good[226] = 26317;
    good[227] = 26437;
    good[228] = 26497;
    good[229] = 26821;
    good[230] = 26833;
    good[231] = 26881;
    good[232] = 26953;
    good[233] = 27073;
    good[234] = 27253;
    good[235] = 27337;
    good[236] = 27361;
    good[237] = 27457;
    good[238] = 27997;
    good[239] = 28057;
    good[240] = 28297;
    good[241] = 28393;
    good[242] = 28813;
    good[243] = 28837;
    good[244] = 28921;
    good[245] = 29101;
    good[246] = 29473;
    good[247] = 29641;
    good[248] = 30181;
    good[249] = 30241;
    good[250] = 30517;
    good[251] = 30553;
    good[252] = 30577;
    good[253] = 30637;
    good[254] = 30661;
    good[255] = 30697;
    good[256] = 30781;
    good[257] = 30853;
    good[258] = 31081;
    good[259] = 31237;
    good[260] = 31321;
    good[261] = 31333;
    good[262] = 31357;
    good[263] = 31477;
    good[264] = 31573;
    good[265] = 31873;
    good[266] = 31981;
    good[267] = 32173;
    good[268] = 32377;
    good[269] = 32497;
    good[270] = 32533;
    good[271] = 32833;
    good[272] = 33037;
    good[273] = 33301;
    good[274] = 33457;
    good[275] = 33493;
    good[276] = 33757;
    good[277] = 33961;
    good[278] = 34057;
    good[279] = 34213;
    good[280] = 34273;
    good[281] = 34381;
    good[282] = 34513;
    good[283] = 34897;
    good[284] = 34981;
    good[285] = 35317;
    good[286] = 35521;
    good[287] = 35677;
    good[288] = 35977;
    good[289] = 36097;
    good[290] = 36241;
    good[291] = 36433;
    good[292] = 36457;
    good[293] = 36793;
    good[294] = 36877;
    good[295] = 36901;
    good[296] = 36913;
    good[297] = 37273;
    good[298] = 37321;
    good[299] = 37357;
    good[300] = 37573;
    good[301] = 37717;
    good[302] = 37957;
    good[303] = 38281;
    good[304] = 38461;
    good[305] = 38833;
    good[306] = 38953;
    good[307] = 38977;
    good[308] = 39217;
    good[309] = 39373;
    good[310] = 39397;
    good[311] = 39733;
    good[312] = 40093;
    good[313] = 40177;
    good[314] = 40213;
    good[315] = 40693;
    good[316] = 40813;
    good[317] = 41017;
    good[318] = 41221;
    good[319] = 41281;
    good[320] = 41413;
    good[321] = 41617;
    good[322] = 41893;
    good[323] = 42061;
    good[324] = 42337;
    good[325] = 42373;
    good[326] = 42793;
    good[327] = 42961;
    good[328] = 43117;
    good[329] = 43177;
    good[330] = 43201;
    good[331] = 43321;
    good[332] = 43573;
    good[333] = 43597;
    good[334] = 43633;
    good[335] = 43717;
    good[336] = 44053;
    good[337] = 44101;
    good[338] = 44221;
    good[339] = 44257;
    good[340] = 44293;
    good[341] = 44893;
    good[342] = 45061;
    good[343] = 45337;
    good[344] = 45433;
    good[345] = 45481;
    good[346] = 45553;
    good[347] = 45613;
    good[348] = 45841;
    good[349] = 46021;
    good[350] = 46141;
    good[351] = 46261;
    good[352] = 46861;
    good[353] = 46993;
    good[354] = 47017;
    good[355] = 47161;
    good[356] = 47353;
    good[357] = 47521;
    good[358] = 47533;
    good[359] = 47653;
    good[360] = 47713;
    good[361] = 47737;
    good[362] = 47797;
    good[363] = 47857;
    good[364] = 48121;
    good[365] = 48193;
    good[366] = 48337;
    good[367] = 48673;
    good[368] = 48757;
    good[369] = 48781;
    good[370] = 49033;
    good[371] = 49261;
    good[372] = 49393;
    good[373] = 49417;
    good[374] = 49597;
    good[375] = 49681;
    good[376] = 49957;
    good[377] = 50221;
    good[378] = 50341;
    good[379] = 50377;
    good[380] = 50821;
    good[381] = 50893;
    good[382] = 51157;
    good[383] = 51217;
    good[384] = 51241;
    good[385] = 51481;
    good[386] = 51517;
    good[387] = 51637;
    good[388] = 52057;
    good[389] = 52081;
    good[390] = 52237;
    good[391] = 52321;
    good[392] = 52453;
    good[393] = 52501;
    good[394] = 52813;
    good[395] = 52861;
    good[396] = 52957;
    good[397] = 53077;
    good[398] = 53113;
    good[399] = 53281;
    good[400] = 53401;
    good[401] = 53917;
    good[402] = 54121;
    good[403] = 54133;
    good[404] = 54181;
    good[405] = 54217;
    good[406] = 54421;
    good[407] = 54517;
    good[408] = 54541;
    good[409] = 54673;
    good[410] = 54721;
    good[411] = 54973;
    good[412] = 55057;
    good[413] = 55381;
    good[414] = 55501;
    good[415] = 55633;
    good[416] = 55837;
    good[417] = 55921;
    good[418] = 55933;
    good[419] = 56053;
    good[420] = 56101;
    good[421] = 56113;
    good[422] = 56197;
    good[423] = 56401;
    good[424] = 56437;
    good[425] = 56701;
    good[426] = 56773;
    good[427] = 56821;
    good[428] = 56857;
    good[429] = 56893;
    good[430] = 57073;
    good[431] = 57097;
    good[432] = 57193;
    good[433] = 57241;
    good[434] = 57373;
    good[435] = 57457;
    good[436] = 57853;
    good[437] = 58153;
    good[438] = 58417;
    good[439] = 58441;
    good[440] = 58537;
    good[441] = 58573;
    good[442] = 58693;
    good[443] = 59053;
    good[444] = 59197;
    good[445] = 59221;
    good[446] = 59281;
    good[447] = 59341;
    good[448] = 59833;
    good[449] = 60217;
    good[450] = 60337;
    good[451] = 60373;
    good[452] = 60637;
    good[453] = 60733;
    good[454] = 60937;
    good[455] = 61057;
    good[456] = 61153;
    good[457] = 61261;
    good[458] = 61297;
    good[459] = 61561;
    good[460] = 61657;
    good[461] = 61681;
    good[462] = 61717;
    good[463] = 61861;
    good[464] = 62137;
    good[465] = 62473;
    good[466] = 62497;
    good[467] = 62533;
    good[468] = 62653;
    good[469] = 62773;
    good[470] = 63313;
    good[471] = 63397;
    good[472] = 63541;
    good[473] = 63697;
    good[474] = 63781;
    good[475] = 63913;
    good[476] = 64153;
    good[477] = 64237;
    good[478] = 64381;
    good[479] = 64513;
    good[480] = 64717;
    good[481] = 65173;
    good[482] = 65293;
    good[483] = 65413;
    good[484] = 65437;
    good[485] = 65497;
    good[486] = 65557;
    good[487] = 65677;
    good[488] = 65881;
    good[489] = 66301;
    good[490] = 66361;
    good[491] = 66601;
    good[492] = 66697;
    good[493] = 66853;
    good[494] = 66973;
    good[495] = 67057;
    good[496] = 67153;
    good[497] = 67273;
    good[498] = 67477;
    good[499] = 67537;
    good[500] = 67741;
    good[501] = 67777;
    good[502] = 67933;
    good[503] = 67993;
    good[504] = 68113;
    good[505] = 68281;
    good[506] = 68521;
    good[507] = 68737;
    good[508] = 69001;
    good[509] = 69073;
    good[510] = 69457;
    good[511] = 69493;
    good[512] = 69697;
    good[513] = 69877;
    good[514] = 70117;
    good[515] = 70177;
    good[516] = 70297;
    good[517] = 70501;
    good[518] = 70621;
    good[519] = 70921;
    good[520] = 70981;
    good[521] = 71233;
    good[522] = 71341;
    good[523] = 71353;
    good[524] = 71593;
    good[525] = 71821;
    good[526] = 72073;
    good[527] = 72481;
    good[528] = 72613;
    good[529] = 72901;
    good[530] = 72937;
    good[531] = 73141;
    good[532] = 73417;
    good[533] = 73477;
    good[534] = 73561;
    good[535] = 73693;
    good[536] = 74077;
    good[537] = 74317;
    good[538] = 74377;
    good[539] = 74713;
    good[540] = 75013;
    good[541] = 75133;
    good[542] = 75181;
    good[543] = 75721;
    good[544] = 75793;
    good[545] = 75913;
    good[546] = 76333;
    good[547] = 76561;
    good[548] = 76597;
    good[549] = 76753;
    good[550] = 77137;
    good[551] = 77641;
    good[552] = 78157;
    good[553] = 78193;
    good[554] = 78277;
    good[555] = 78877;
    good[556] = 78901;
    good[557] = 79333;
    good[558] = 79357;
    good[559] = 79537;
    good[560] = 79657;
    good[561] = 79693;
    good[562] = 79801;
    good[563] = 79873;
    good[564] = 80077;
    good[565] = 80173;
    good[566] = 80221;
    good[567] = 80473;
    good[568] = 80701;
    good[569] = 80713;
    good[570] = 80917;
    good[571] = 81013;
    good[572] = 81181;
    good[573] = 81517;
    good[574] = 81637;
    good[575] = 81853;
    good[576] = 82021;
    good[577] = 82153;
    good[578] = 82261;
    good[579] = 82561;
    good[580] = 82981;
    good[581] = 83077;
    good[582] = 83221;
    good[583] = 83233;
    good[584] = 83437;
    good[585] = 83617;
    good[586] = 83701;
    good[587] = 83773;
    good[588] = 84121;
    good[589] = 84313;
    good[590] = 84673;
    good[591] = 84697;
    good[592] = 84793;
    good[593] = 84913;
    good[594] = 85297;
    good[595] = 85333;
    good[596] = 85453;
    good[597] = 85717;
    good[598] = 85933;
    good[599] = 86353;
    good[600] = 86413;
    good[601] = 87181;
    good[602] = 87253;
    good[603] = 87337;
    good[604] = 87421;
    good[605] = 87433;
    good[606] = 87517;
    good[607] = 87553;
    good[608] = 87973;
    good[609] = 88117;
    good[610] = 88177;
    good[611] = 88237;
    good[612] = 88261;
    good[613] = 88513;
    good[614] = 88741;
    good[615] = 88897;
    good[616] = 88993;
    good[617] = 89293;
    good[618] = 89833;
    good[619] = 89917;
    good[620] = 90121;
    good[621] = 91081;
    good[622] = 91381;
    good[623] = 91393;
    good[624] = 91513;
    good[625] = 91957;
    good[626] = 92041;
    good[627] = 92557;
    good[628] = 92761;
    good[629] = 92821;
    good[630] = 92893;
    good[631] = 92941;
    good[632] = 93097;
    good[633] = 93133;
    good[634] = 93493;
    good[635] = 93637;
    good[636] = 93913;
    good[637] = 94033;
    good[638] = 94117;
    good[639] = 94273;
    good[640] = 94321;
    good[641] = 94441;
    good[642] = 94573;
    good[643] = 94777;
    good[644] = 94837;
    good[645] = 94993;
    good[646] = 95257;
    good[647] = 95317;
    good[648] = 95401;
    good[649] = 95581;
    good[650] = 95617;
    good[651] = 95713;
    good[652] = 95737;
    good[653] = 96097;
    good[654] = 96157;
    good[655] = 96181;
    good[656] = 96493;
    good[657] = 96517;
    good[658] = 96973;
    good[659] = 97081;
    good[660] = 97177;
    good[661] = 97501;
    good[662] = 97561;
    good[663] = 97777;
    good[664] = 97813;
    good[665] = 98017;
    good[666] = 98737;
    good[667] = 98953;
    good[668] = 99277;
    good[669] = 99577;
    good[670] = 99661;
    good[671] = 99877;
    good[672] = Inf;
}

int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("in.txt", "r", stdin);
//    //    freopen("out.txt", "w", stdout);
//#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    magic();
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;

        auto itGoodL = lower_bound(good.begin(), good.end(), l);
        auto itGoodR = lower_bound(good.begin(), good.end(), r);
        if (*itGoodR > r) --itGoodR;
        int d = itGoodR - itGoodL;
        cout << max(d + 1, 0) << endl;
    }

    return 0;
}


Measured memory_bytes: 640