#include <bits/stdc++.h>
using namespace std;
int x[10][1000005],n,i,ma,mx,j,k,m,pr[1000005];
int main()
{
    freopen("divprim.in","r",stdin);
    ofstream g ("divprim.out");
    scanf("%d",&n);
    mx=1000000;
    for(i=2; i<=mx; ++i)
        if(!pr[i])
            for(j=i; j<=mx; j+=i)
                pr[j]++;
    for(i=1; i<=mx; ++i)
        x[pr[i]][i]=i;
    for(i=1; i<=7; ++i)
        for(j=1; j<=mx; ++j)
            x[i][j]=max(x[i][j],x[i][j-1]);
    for(i=1; i<=n; ++i)
    {
        scanf("%d%d",&m,&k);
        g<<x[k][m]<<'\n';
    }
    return 0;
}