#include <stdio.h>
#include <stdlib.h>

char ciur[1000000];

int main() {
    int t, n, k, d, i, j;
    FILE *fin, *fout;
    fin = fopen ("divprim.in", "r");
    fout = fopen ("divprim.out", "w");
    fscanf(fin, "%d", &t);
    ciur [0] = ciur[1] = 0;
    for (d = 2; d <= 1000000; d++){
        if (ciur[d] == 0){
            for (i = d ; i <= 1000000; i += d) {
                ciur[i]++;
            }
        }
    }
    for (i = 0; i < t; i++){
        fscanf(fin, "%d %d", &n, &k);
        j = n - 1;
        while (j > 0 && ciur[j] != k)
            j = j - 1;
        fprintf(fout, "%d\n", j);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}