#include <cstdio>
#define NMAX 1000005
#define TMAX 100005

using namespace std;

int t, n[TMAX], k[TMAX], ciurp[NMAX], vmax=0;

void umple()
{
    for(int i=2; i<=vmax; i++)
        ciurp[i]=-1;
}

void ciurul()
{
    for(int i=2; i<=vmax; i++)
    {
        if(ciurp[i] == -1)
        {
            for(int j=2*i; j<=vmax; j+=i)
                ciurp[j]++;
            ciurp[i]=0;
        }
    }
}


int dprim(int n, int k)
{
    while(n!=0)
    {
        if(ciurp[n]==k-1)
            return n;
        n--;
    }
    return 0;
}

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);


    scanf("%d", &t);
    for(int i=1; i<=t; i++)
    {
        scanf("%d %d", &n[i], &k[i]);
        if(n[i]>vmax)
            vmax=n[i];
    }
    umple();
    ciurul();
    for(int i=1; i<=t; i++)
    {
        printf("%d\n", dprim(n[i], k[i]));
    }

    return 0;
}