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

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

bool C[N+5];
int div[N+5];
int a[10][N+5];
int Q;

void Ciur()
{
    int i,j;
    C[2]=1;
    for(i=3; i<=N; i+=2)
        C[i]=1;
    for(i=3; i*i<=N; i+=2)
        if(C[i])
            for(j=i*i; j<=N; j+=2*i)
                C[j]=0;
}

void Prelucrare()
{
    int i,j;
    for(i=2; i<=N; i+=2)
        div[i]++;
    for(i=3; i<=N; i+=2)
        if(C[i])
            for(j=i; j<=N; j+=i)
                div[j]++;
}

int CB(int nr,int k)
{
    int st,dr,mij;
    int possible_number;
    if(k==0) return 1;
    if(nr<a[k][1]) return 0;
    if(nr>a[k][a[k][0]]) return a[k][a[k][0]];
    st=1;
    dr=a[k][0];
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[k][mij]==nr) return nr;
        else if(a[k][mij]<nr)
        {
            possible_number=a[k][mij];
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return possible_number;
}

void Rezolvare()
{
    int i;
    int nr,k;
    for(i=1; i<=N; ++i)
        a[div[i]][++a[div[i]][0]]=i;

    fin>>Q;
    for(i=1; i<=Q; ++i)
    {
        fin>>nr>>k;
        fout<<CB(nr,k)<<"\n";
    }
}




int main()
{
Ciur();
Prelucrare();
Rezolvare();
fin.close();
fout.close();
    return 0;
}