#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
unsigned long long int t,n,k,i,j,a[1000001];
unsigned long long int cautbin(unsigned long long int val)
{
    unsigned long long int step=(1<<18), start = 1;
    for(;step;step>>=1)
    {
        unsigned long long int index=step+start;
        if(index>10) continue;
        if(a[index]<=val)
        start=index;
    }
    return start;
}
int main()
{
    a[1]=0;
    for (i=2;i<=1000000;i++)
        a[i]=1;

    for (i=2;i<=1000000;i++)
        if (a[i]==1)
        {
            for (j=i*2;j<=1000000;j+=i)
                a[j]++;
        }
    for (i=2;i<=1000000;i++)
        a[i]--;

    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>n;
        fin>>k;
        if(a[cautbin(k)]==k)
            fout<<cautbin(k)<<"\n";
        else
            fout<<0<<"\n";
    }
}