#include <cstdio>
//#include <iostream>
#define MAX 1000001
using namespace std;
int p[1000099];
int main()
{
   int t,k,n,i,j;
   for(i=2;i<=MAX;i+=2)
        p[i]++;
   for(i=3;i<=1000;i+=2)
    {
        if(p[i]==0)
            for(j=i;j<=MAX;j+=i)
                p[j]++;
    }
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++)
        {
            scanf("%d %d",&n,&k);
            j=n;
            while(p[j]!=k and j>0)j--;
            printf("%d\n",j);
        }
    return 0;
}