#include <cstdio>
#define Max 1000000
#define Max2 500000
using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
int ciur[Max+1]={0};
int v[8][100000];

int main()
{int i,j,n,k;
for (i=2;i<=Max2;i++) if (ciur[i]==0) for (j=2*i;j<=Max;j+=i) ciur[j]++;

int t;fscanf(f,"%d",&t);
for (i=1;i<=t;i++) {fscanf(f,"%d %d",&n,&k);
                    ciur[0]=k;
                    j=n;
                    while (ciur[j]!=k) j--;
                    fprintf(g,"%d\n",j);
                    }


return 0;
}