#include <stdio.h>
#include <fstream.h>
#include <iostream.h>

int n, contor=0, k, t;
char prim[1000001];
//int test[100001];
int main(void)
{
    int i, j, l;
    prim[1]=0;
    for (i=2;i<=1000001;i++)
        prim[i]=1;
    for (i=2;i<=1000001;i++)
        if(prim[i]==1)
        {
           
            for (j=i+i;j<=1000001;j=j+i)
                prim[j]++;
        }
 
    
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>t;
   // for(i=1;i<=t;i++)
  //  test[i]=0;
    for(i=1;i<=t;i++)
       {f>>n>>k;
        if(k>1)
        {for(l=n;l>1;l--)
         if(prim[l]==k+1) {g<<l<<"\n"; break;}}
        else for(l=n;l>1;l--)
         if(prim[l]==1||prim[l]==2) {g<<l<<"\n"; break;}
       }
    //for(i=1;i<=t;i++)
     // g<<test[i]<<endl; 
      
    f.close();
    g.close();
    return 0;
}