#include <bits/stdc++.h>
#define NMAX 1000001

using namespace std;
int fact[NMAX];/// fact [i] = idadi ya mambo ya kwanza ya i
int ans[NMAX][10];///jibu lol :)
void ciur_smart ()
{
    for(int i=2;i<=NMAX;++i)
    {
        if(fact[i]==0)
        {
            for(int j=i;j<=NMAX;j+=i)
            {
                fact[j]++;
            }
        }
    }
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur_smart();
    for(int i=1;i<=NMAX;++i)
    {
        ans[i][fact[i]]=i;///hata idadi
    }
    for(int j=1;j<=7;++j)
    {
        for(int i=1;i<=NMAX;++i)
        {
            if(!ans[i][j])
                ans[i][j]=ans[i-1][j];///kwa sababu itakamilika na majibu ya awali, sawa na nguvu
        }
    }
    int t,n,k;
    scanf("%d",&t);
    while(t--)///vipimo
    {
        scanf("%d %d",&n,&k);
        printf("%d\n",ans[n][k]);
    }
    return 0;
}