#include <cstdio>

using namespace std;
int ciur[1000001];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int t,n,k,i,j,cnt,t1;
    scanf("%d",&t);
    for(i=2;i<=1000000;i=i+2)
        ciur[i]++;
    for(i=3;i<=1000000;i=i+2)
       if(!ciur[i])
        for(j=i;j<=1000000;j=j+i)
          ciur[j]++;
    for(t1=1;t1<=t;t1++)
    {
    scanf("%d%d",&n,&k);
    cnt=0;
    for(i=2;i<=n;i++)
        if(i>cnt && ciur[i]==k)
            cnt=i;
    printf("%d\n",cnt);
    }
    return 0;
}