#include<stdio.h>
#define N 1000000
int ciur[N+1];
int nr[8][N+1];
int pred[8];
int main()
{
    FILE *fin,*fout;
    fin=fopen("divprim.in","r");
    fout=fopen("divprim.out","w");
    int n;
    fscanf(fin,"%d",&n);
    int i;
    for(i=2;i<1000;i++)
    {
        if(ciur[i]==0)
        {
            int j;
            for(j=i*2;j<=N;j+=i)
                ciur[j]++;
        }
    }
    pred[0]=1;
    for(i=1;i<=1000000;i++)
    {
        if(ciur[i]==0&&i!=1)
            ciur[i]=1;
        pred[ciur[i]]=i;
        int j;
        for(j=0;j<=7;j++)
            nr[ciur[j]][i]=pred[ciur[j]];
    }
    for(i=0;i<n;i++)
    {
        int limita,k;
        fscanf(fin,"%d%d",&limita,&k);
        fprintf(fout,"%d\n",nr[k][limita]);
    }
    return 0;
}