#include <cstdio>
using namespace std;

const int NMAX = 8e4;

int v[NMAX], k[NMAX], ciur[1000001], mx, i, j, t;

void ciur1(int n)
{
    for (int i = 2 * n; i <= mx; i += n)
        ciur[i]++;
}

int main()
{
	freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
	scanf("%d", &t);
    int c[9];
    c[1] = 2;
    c[2] = 3 * c[1];
    c[3] = 5 * c[2];
    c[4] = 7 * c[3];
    c[5] = 11 * c[4];
    c[6] = 13 * c[5];
    c[7] = 17 * c[6];
    c[8] = 19 * c[7];
    for (int i = 1; i <= t; i++)
    {
		scanf("%d%d", &v[i], &k[i]);
        if (v[i] > mx)
            mx = v[i];
    }
    ciur1(2);
    ciur[2] = 1;
    for (i = 3; i <= mx; i+=2)
        if (ciur[i] == 0)
        {
            ciur1(i);
            ciur[i] = 1;
        }
    for (i = 1; i <= t; i++)
    {
         int ok = 0;
         if (k[i] == 0 && v[i] > 1)
         {
			 printf("1 ");
             ok = 1;
         }
         else
        while (ciur[v[i]] != k[i])
        {
            if (v[i] <= c[k[i]] - 1)
            {
                ok = 1;
                printf("0\n");
                break;
            }
            v[i]--;
        }
        if(ok==0)
			printf("%d\n", v[i]);
    }
}