#include <cstdio>

#define maxN 1000000
#define maxK 7

using namespace std;

int sieve[maxN+1], dp[maxN+1][maxK+1];

void sieveOfEratosthenes(){
    int i, j;
    for (i=2; i<=maxN; i+=2)
        sieve[i]=1;
    for (i=3; i*i<=maxN; i++)
        if (sieve[i]==0)
            for (j=i; j<=maxN; j+=i)
                sieve[j]++;
}

void precalculate(){
    sieveOfEratosthenes();
    int i, j;
    for (i=1; i<=maxN; i++)
        for (j=0; j<=maxK; j++)
            if (sieve[i]==j)
                dp[i][j]=i;
            else dp[i][j]=dp[i-1][j];
}

int main(){
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    precalculate();
    int T, N, K;
    scanf("%d", &T);
    while (T--){
        scanf("%d%d", &N, &K);
        printf("%d\n", dp[N][K]);
    }
    return 0;
}