#include <iostream>
using namespace std;
int main()
{
int test;
cin >> test;
for (int i = 0; i < test; i++)
{
int a, b;
cin >> a >> b;
//deklaracja tablicy bool wypełnionej zerami
bool tab[b+1] = {};
//sito eratostenesa
for (int x = 2; x * x <= b; x++)
if (tab[x] != true)
for (int y = x * x; y <= b; y += x)
tab[y] = true;
//zliczanie liczb pierwszych w zadanym przedziale
int n = 0;
for (int i = a; i <= b; i++)
if(tab[i] == false)
n++;
//wyjscie
cout << n << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKQp7CiAgICBpbnQgdGVzdDsKICAgIGNpbiA+PiB0ZXN0OwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCB0ZXN0OyBpKyspCiAgICB7CiAgICAgICAgaW50IGEsIGI7CiAgICAgICAgY2luID4+IGEgPj4gYjsKICAgICAgICAvL2Rla2xhcmFjamEgdGFibGljeSBib29sIHd5cGXFgm5pb25laiB6ZXJhbWkKICAgICAgICBib29sIHRhYltiKzFdID0ge307CiAgICAgICAgLy9zaXRvIGVyYXRvc3RlbmVzYQogICAgICAgIGZvciAoaW50IHggPSAyOyB4ICogeCA8PSBiOyB4KyspCiAgICAgICAgICAgIGlmICh0YWJbeF0gIT0gdHJ1ZSkKICAgICAgICAgICAgICAgIGZvciAoaW50IHkgPSB4ICogeDsgeSA8PSBiOyB5ICs9IHgpCiAgICAgICAgICAgICAgICAgICAgdGFiW3ldID0gdHJ1ZTsKICAgICAgICAvL3psaWN6YW5pZSBsaWN6YiBwaWVyd3N6eWNoIHcgemFkYW55bSBwcnplZHppYWxlCiAgICAgICAgaW50IG4gPSAwOwogICAgICAgIGZvciAoaW50IGkgPSBhOyBpIDw9IGI7IGkrKykKICAgICAgICAgICAgaWYodGFiW2ldID09IGZhbHNlKQogICAgICAgICAgICAgICAgbisrOwogICAgICAgIC8vd3lqc2NpZQogICAgICAgIGNvdXQgPDwgbiA8PCBlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=