#include <bits/stdc++.h>
using namespace std;
int T,n,k;
#define NMAX 1000000
bool notPrime[NMAX+5];
int D[8][NMAX+5],nr[NMAX+5];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    D[0][2]=2;
    for (int i=4;i<=NMAX;i+=2)
    {
        notPrime[i]=true;
        D[1][i]=i;
        nr[i]=1;
    }
    for (int i=3;i<=NMAX;i+=2)
    {
        if (!notPrime[i])
        {
            for (int j=i+i;j<=NMAX;j+=i)
            {
                notPrime[j]=true;
                D[nr[j]][j]=0;
                nr[j]++;
                if (nr[j]<=7)
                    D[nr[j]][j]=j;
            }
        }
        else D[0][i]=i;
    }
    for (int k=0;k<=7;k++)
        for (int i=2;i<=NMAX;i++)
            if (!D[k][i])
                D[k][i]=D[k][i-1];
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d %d",&n,&k);
        printf("%d\n",D[k][n]);
    }
    return 0;
}