#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int n;
int ndp[1000001];
int sol[1000001][8];

int divprim(int x)
{
    int i,nr=0,u=x;
    for(i=2;i<=u;i++)
        if(x%i==0)
       {
            nr++;
            while(x%i==0)
                x=x/i;
       }
       return nr;
}

int dei(int st,int dr, int r)
{

    if(st==dr)
    if(ndp[st]==r)
            return st;
        else
            return 0;

 int mijl=(st+dr)/2;
    int max1=dei(st,mijl,r);
    int max2=dei(mijl+1,dr,r);

    return max(max1,max2);

}

int main()
{
    fin>>n;
    int i,r,q;
    int j;

    for(i=2;i<=1000000;i++)
        if(ndp[i]==0)
        for(j=i;j<=1000000;j=j+i)
        ndp[j]++;

    for(i=1;i<=n;i++)
    {
        fin>>q>>r;
        fout<<dei(2,q,r)<<'\n';
    }



    return 0;
}