#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) {test[i]=l; l=1;}}
        else for(l=n;l>1;l--)
         if(prim[l]==1||prim[l]==2) {test[i]=l; l=1;}
       }
    for(i=1;i<=t;i++)
      g<<test[i]<<endl; 
      
    f.close();
    g.close();
    return 0;
}