#include <stdio.h>
typedef unsigned long long ulong;
// Funkcja mnoży a i b mod n
ulong MnozModulo(ulong a, ulong b, ulong n)
{
ulong m,w;
w = 0;
for(m = 1; m; m <<= 1)
{
if(b & m)
w = (w + a) % n;
a = (a << 1) % n;
}
return w;
}
// Funkcja oblicza a^e mod n
ulong PotegujModulo(ulong a, ulong e, ulong n)
{
ulong m,p,w;
p = a;
w = 1;
for(m = 1; m; m <<= 1)
{
if(e & m)
w = MnozModulo(w,p,n);
p = MnozModulo(p,p,n);
}
return w;
}
int main()
{
int test,p,b,ile;
ulong d,x;
ulong a[3];
a[1]=2;
a[2]=3;
int i,j,s,n;
bool t;
scanf("%d",&test);
while(test--)
{
scanf(" %d %d",&p,&b);
ile=0;
do
{
if(p==2)
ile++;
else if(p%2)
{
s=0;
for(d=p - 1; d % 2 == 0; s++)
d /= 2;
t = true;
for(i = 1; i <= 2; i++)
{
x = PotegujModulo(a[i],d,p);
if((x == 1) || (x == p - 1))
continue;
for(j = 1; (j < s) && (x != p - 1); j++)
{
x = MnozModulo(x,x,p);
if(x == 1)
{
t = false;
break;
}
}
if(!t)
break;
if(x != p - 1)
{
t = false;
break;
}
}
if(t)
ile++;
}
p++;
}
while(p<=b);
printf("%d\n",ile);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+Cgp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bG9uZzsKCi8vIEZ1bmtjamEgbW5vxbx5IGEgaSBiIG1vZCBuCnVsb25nIE1ub3pNb2R1bG8odWxvbmcgYSwgdWxvbmcgYiwgdWxvbmcgbikKewogICAgdWxvbmcgbSx3OwoKICAgIHcgPSAwOwogICAgZm9yKG0gPSAxOyBtOyBtIDw8PSAxKQogICAgewogICAgICAgIGlmKGIgJiBtKQogICAgICAgICAgICB3ID0gKHcgKyBhKSAlIG47CiAgICAgICAgYSA9IChhIDw8IDEpICUgbjsKICAgIH0KICAgIHJldHVybiB3Owp9Ci8vIEZ1bmtjamEgb2JsaWN6YSBhXmUgbW9kIG4KdWxvbmcgUG90ZWd1ak1vZHVsbyh1bG9uZyBhLCB1bG9uZyBlLCB1bG9uZyBuKQp7CiAgICB1bG9uZyBtLHAsdzsKCiAgICBwID0gYTsKICAgIHcgPSAxOwogICAgZm9yKG0gPSAxOyBtOyBtIDw8PSAxKQogICAgewogICAgICAgIGlmKGUgJiBtKQogICAgICAgICAgICB3ID0gTW5vek1vZHVsbyh3LHAsbik7CiAgICAgICAgcCA9IE1ub3pNb2R1bG8ocCxwLG4pOwogICAgfQogICAgcmV0dXJuIHc7Cn0KCmludCBtYWluKCkKewogICAgaW50IHRlc3QscCxiLGlsZTsKICAgIHVsb25nIGQseDsKICAgIHVsb25nIGFbM107CiAgICBhWzFdPTI7CiAgICBhWzJdPTM7CiAgICBpbnQgaSxqLHMsbjsKICAgIGJvb2wgdDsKICAgIHNjYW5mKCIlZCIsJnRlc3QpOwogICAgd2hpbGUodGVzdC0tKQogICAgewogICAgICAgIHNjYW5mKCIgJWQgJWQiLCZwLCZiKTsKICAgICAgICBpbGU9MDsKICAgICAgICBkbwogICAgICAgIHsKICAgICAgICAgICAgaWYocD09MikKICAgICAgICAgICAgICAgIGlsZSsrOwogICAgICAgICAgICBlbHNlIGlmKHAlMikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcz0wOwogICAgICAgICAgICAgICAgZm9yKGQ9cCAtIDE7IGQgJSAyID09IDA7IHMrKykKICAgICAgICAgICAgICAgICAgICBkIC89IDI7CiAgICAgICAgICAgICAgICB0ID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGZvcihpID0gMTsgaSA8PSAyOyBpKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgeCA9IFBvdGVndWpNb2R1bG8oYVtpXSxkLHApOwogICAgICAgICAgICAgICAgICAgIGlmKCh4ID09IDEpIHx8ICh4ID09IHAgLSAxKSkKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgZm9yKGogPSAxOyAoaiA8IHMpICYmICh4ICE9IHAgLSAxKTsgaisrKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgeCA9IE1ub3pNb2R1bG8oeCx4LHApOwogICAgICAgICAgICAgICAgICAgICAgICBpZih4ID09IDEpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHQgPSBmYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGlmKCF0KQogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICBpZih4ICE9IHAgLSAxKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdCA9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZih0KQogICAgICAgICAgICAgICAgICAgIGlsZSsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHArKzsKICAgICAgICB9CiAgICAgICAgd2hpbGUocDw9Yik7CiAgICAgICAgcHJpbnRmKCIlZFxuIixpbGUpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=