#include <stdio.h>

int primes[78498] = {2};

int PrimeNumbersSieve5(int N){

int i, j, k = 0;

for(i = 1; ((i * i) << 1) + (i << 1) <= N; i += 1){
    if((list[i >> 3] & (1 << (i & 7))) == 0){
        for(j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= N; j += (i << 1) + 1){
             list[j >> 3] |= (1 << (j & 7));
        }
    }
}
for (i = 1; 2 * i + 1 <= N; ++i){
    if((list[i >> 3] & (1 << (i & 7))) == 0){
        primes[++k] = 2 * i + 1;
    }
}
return primes;
}

int main(){

FILE *file1, *file2;
int T, N, K, i, j, divPrim, ans;

file1 = fopen("divprim.in", "r");
file2 = fopen("divprim.out", "w");

PrimeNumbersSieve5(1000000);

fscanf(file1, "%d", &T);

while(T--){

    fscanf(file1, "%d", &N);
    fscanf(file1, "%d", &K);
    ans = 0;

    for(j=N; j>0; j--){
        divPrim = 0;

        for(i=0; i<78498; i++){
            if(primes[i]>j/2){
                break;
            }
            if(!(j%primes[i])){
                divPrim++;
            }
        }
        if(divPrim==K){
            fprintf(file2, "%d\n", j);
            ans = 1;
            break;
        }
    }
    if(!ans){
        fprintf(file2, "0\n");
    }
}
return 0;
}