#include<stdio.h>

int vector[1000001];
int limits[7] = {1, 78737, 288725,
  379720, 208034, 42492, 2285, 8};

struct kappa{
    int iterator;
    int indices[379720];
}kappa[7];

int ciur(int N){

int i, j;

for(i=2; i<=N; i++){
    if(!vector[i]){
        for(j=i; j<=N; j+=i){
            vector[j]++;
        }
    }
}
}
int search(n, k){

int low = 0;
int high = limits[k] - 1;
int result = -1;

while(low<=high){
    int mid = (low+high)/2;
    if(kappa[k].indices[mid]<=n){
        result = mid;
        low = mid;
    }else if(kappa[k].indices[mid]>n){
        high = mid;
    }
}
return result;
}

int main(){

FILE *file1, *file2;
int T, N, K, i, found;

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

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

for(i=0; i<=7; i++){
    kappa[i].iterator = 0;
}
for(i=1; i<1000001; i++){
    kappa[vector[i]].indices[kappa[vector[i]].iterator++] = i;
}

while(T--){
    fscanf(file1, "%d", &N);
    fscanf(file1, "%d", &K);

    found = search(N, K);
    if(found!=-1){
        fprintf(file2, "%d\n", kappa[K].indices[found]);
    }else{
        fprintf(file2, "0\n");
    }
}
return 0;
}