#include<bits/stdc++.h>
using namespace std;
int m[80000],kk=0,h,a,b;
int main()
{
for(int i=2;i<=1000000;i++)
{
int f=0;
for(int j=2;j*j<=i;j++)
if(i%j==0)
{
f=1;
break;
}
if(f==0)
{
kk++;
m[kk]=i;
}
}
int k,u=0;
cin>>k;
while(u<k)
{
u++;
scanf("%d%d",&a,&b);
h=1;
while(m[h]<a&&h<=kk)
{
if(m[h+1000]<a&&h+1000<=kk)h+=1000;
else h++;
}
int hh=h;
h=1;
while(m[h]<b&&h<=kk)
{
if(m[h+1000]<b&&h+1000<=kk)h+=1000;
else h++;
}
if(m[h]!=b)h--;
if(h<hh||h==hh)
{
if(h<hh)cout<<0<<endl;
else cout<<1<<endl;
continue;
}
cout<<h-hh+1<<endl;
}
return 0;
}

#include <iostream>
using namespace std;

int ackermann(int m, int n) {
if (m == 0) {
return n + 1;
} else if (n == 0) {
return ackermann(m - 1, 1);
} else {
return ackermann(m - 1, ackermann(m, n - 1));
}
}

int main() {
int m, n;
cin >> m >> n;
cout << ackermann(m, n);
return 0;
}//一定对，不对我倒立