#include <stdio.h>

const int NMAX = 1000000;
int test,nrdiv[NMAX + 5],sol[NMAX + 5][8];

void sieve(){
    for(int i = 2;i <= NMAX;i++){
        if(!nrdiv[i])
            for(int j = i;j <= NMAX;j += i)
                nrdiv[j]++;
        sol[i][nrdiv[i]] = i;
    }
    for(int j = 0;j < 8;j++)
        for(int i = 2;i <= NMAX;i++)
            if(!sol[i][j])
                sol[i][j] = sol[i - 1][j];
}

int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    
    scanf("%d",&test);
    sieve();
    
    while (test--) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",sol[x][y]);
    }
    
    return 0;
}