#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define NMAX 1000005
using namespace std;
int nrprim[NMAX];
int divprimi[NMAX];
void prim()
{int i,j;

    for (i=1;i<=NMAX;i++)
    nrprim[i]=1;
    for (i=2;i<=NMAX;i++)
       if ((nrprim[i]) )
            
        {divprimi[i]=1;
         for (j=2*i;j<=NMAX;j+=i)
           {nrprim[j]=0;divprimi[j]++;}
        }}      
 
int main()
{int ct,n,k,t,j,i,ok;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    prim();
    
    for (i=1;i<=t;i++)
    {
        scanf("%d %d",&n,&k);
    
    ok = 0;ct=0;
    for (j=n;j>=2;j--)
    {
    if (divprimi[j] == k)
    {
           ok = 1;
           printf("%d\n",j);
           break;
    }
    }
    if (ok==0) printf("0\n");
    }
    
return 0;
}