#include <stdio.h>
short int ciur[1000001];
int main()
{
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    for(int i=4;i<=1000000;i+=2) ciur[i]++;
    for(int i=3;i<=1000000;i+=2)
    {
            if(ciur[i]==0)
            {
                          for(int j=i;j<=1000000/i;j+=2) ciur[i*j]++;
            }
    }
    int t,n,k;
    scanf("%d",&t);
    for(int x=1;x<=t;x++)
    {
            scanf("%d%d",&n,&k);
            ciur[0]=k;
            for(int i=n;;i--)
            {
                    if(ciur[i]==k)
                    {
                        printf("%d\n",i);
                        break;          
                    }
            }
    }
}