#include <stdio.h>
#define nmax 1000010

using namespace std;

int tt,n,k;
int fr[nmax],prime[nmax];
int dp[8][nmax];

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);

    scanf("%d",&tt); fr[1]=1;

    for (int i=2;i*i<=1e6;i++)
        if (fr[i]==0) {
            for (int j=i*i;j<=1e6;j+=i) fr[j]=1;
    }

    for (int i=2;i<=1e6;i++)
        if (fr[i]==0) {
            for (int j=i;j<=1e6;j+=i) prime[j]++;
    }

    for (int i=0;i<=7;i++) {

        for (int j=1;j<=1e6;j++)
            if (prime[j]==i) dp[i][j]=j; else
               dp[i][j]=dp[i][j-1];
    }

    for (int o=1;o<=tt;o++) {
        scanf("%d %d",&n,&k);
        printf("%d\n",dp[k][n]);
    }

    return 0;
}