#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=

NAoxIDUKMiA1CjEgNgoyIDYK

4
1 5
2 5
1 6
2 6