#include <iostream>
#include <stdio.h>
#define MAX 1000001

FILE *f, *g;

using namespace std;
int d[MAX];
void nrdiv()
{
    int i, j;
    for(i = 2; i < MAX; i++)
        if (d[i] == 0)
            for(j = i; j < MAX; j += i)
                d[j]++;

}

int main()
{   int n, x, y, aux, i;
    f = fopen("divprim.in", "r");
    fscanf(f, "%d", &n);
    nrdiv();
    g = fopen("divprim.out", "w");
    for(i = 1; i <= n; i++)
    {
        fscanf(f, "%d%d", &x, &y);
        int j = 0;
        aux = 0;
        while(j <= x)
        {
            if(d[j] == y)
                aux = j;
            j++;
        }
        fprintf(g,"%d\n", aux);
    }
    fclose(f);
    fclose(g);
    return 0;
}