#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
ll arr[20000011];
bool prime[20000011];
int main()
{
ll a,b,c,d,e,f,g,h;
cin>>a;arr[0]=0;
for(b=1;b<=20000011;b++)
{arr[b] = __builtin_popcount(b) + arr[b-1];}
memset(prime,false,sizeof(prime));
//prime[1] = true;
for(b=2;b<=sqrt(20000011);b++)
{
if(prime[b]==false)
{
for(c=b*2;c<=20000011;c=c+b)
{
prime[c] = true;
}
}
}
for(b=0;b<a;b++)
{
cin>>c>>d;
e = arr[d]-arr[c-1];
if(e==1)cout<<"1\n";
else
{
while(1)
{
if(prime[e]==false)
{
cout<<e*2<<"\n";break;
}
else e++;
}
}
}
}
ICNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgogICAgdHlwZWRlZiAgbG9uZyBsb25nIGludCBsbDsKICAgCiAgICB1c2luZyBuYW1lc3BhY2Ugc3RkOwogICAgbGwgYXJyWzIwMDAwMDExXTsKICAgIGJvb2wgcHJpbWVbMjAwMDAwMTFdOwogICAgaW50IG1haW4oKQogICAgewogICAgICAgbGwgYSxiLGMsZCxlLGYsZyxoOwogICAgICAgY2luPj5hO2FyclswXT0wOwogICAgICAgZm9yKGI9MTtiPD0yMDAwMDAxMTtiKyspCiAgICAgICB7YXJyW2JdID0gX19idWlsdGluX3BvcGNvdW50KGIpICsgYXJyW2ItMV07fQoKICAgICAgICBtZW1zZXQocHJpbWUsZmFsc2Usc2l6ZW9mKHByaW1lKSk7Ci8vcHJpbWVbMV0gPSB0cnVlOwogICAgICAgIGZvcihiPTI7Yjw9c3FydCgyMDAwMDAxMSk7YisrKQogICAgICAgIHsKICAgICAgICAgICAgaWYocHJpbWVbYl09PWZhbHNlKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGM9YioyO2M8PTIwMDAwMDExO2M9YytiKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwcmltZVtjXSA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgfQogICAgICAgZm9yKGI9MDtiPGE7YisrKQogICAgICAgewogICAgICAgICAgY2luPj5jPj5kOwogICAgICAgICAgICBlID0gYXJyW2RdLWFycltjLTFdOwogICAgICAgICAgICBpZihlPT0xKWNvdXQ8PCIxXG4iOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHdoaWxlKDEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihwcmltZVtlXT09ZmFsc2UpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY291dDw8ZSoyPDwiXG4iO2JyZWFrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBlKys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgIH0KICAgIH0K