#include <fstream>
#define N 1300005
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int T;
bool c[N];
int d[1000005];
int a[8][400000];

int main()
{
    int i,j,ct=1;
    c[2]=1;
    for(i=3; i<=N; i+=2) c[i]=1;
    for(i=3; i*i<=N; i+=2)
        if(c[i]==1)
             for(j=i*i; j<=N; j+=2*i)
                c[j]=0;
    /// d[i] = nr de divizori primi
    for(i=2; i<=N; i+=2) d[i]=1;
    for(i=3; i<=N; ++i)
        if(c[i]==1)
            for(j=i; j<=N; j+=i) d[j]++;

    /// a[i][j] = matricea numerelor cu cel mult 7 divizori
    for(i=2; i<=N; ++i)
        if(d[i]<=7)
            a[d[i]][++a[d[i]][0]]=i;

    int x,y;
    fin>>T;
    for(i=1; i<=T; ++i)
    {
        fin>>x>>y;
        if(x<a[y][1]) fout<<0<<"\n";
        else if(x>a[y][a[y][0]]) fout<<a[y][ a[y][0] ]<<"\n";
        else
        {
            int st=1,dr=a[y][0],mij,poz;
            while(st<=dr)
            {
                mij=st+(dr-st)/2;
                if(x==a[y][mij]) poz=mij;
                else if(x<a[y][mij]) dr=mij-1;
                else poz=mij,st=mij+1;
            }
            fout<<a[y][poz]<<"\n";
        }
    }
    return 0;
}