#include <cstdio>
using namespace std;
int c[1000001], a[10][1000010];
void ciur(){
    int i, j;
    for(i = 2; i <= 1000000; i ++){
        if(!c[i]){
            for(j = 2 * i; j <= 1000000; j += i)
                c[j]++;
            c[i]=1;
        }
    }
}
int main(){
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    int n, t, k, i, j;
    scanf("%d", &t);
    ciur();
    for(i = 1; i <= 7; i ++){
        for(j = 1; j <= 1000000; j ++){
            if (c[j] == i)
                a[i][j] = j;
            else
                a[i][j] = a[i][j - 1];
        }
    }
    for(i = 1; i <= t; i++){
        scanf("%d%d", &n, &k);
        printf("%d\n", a[k][n]);
    }
    return 0;
}