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

int n, contor=0, k, t;
char prim[1000001];
 
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]=0;
        }
 
    
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>t;
    for(i=1;i<=t;i++)
       {f>>n>>k;
        for(l=n;l>=1;l--)
         if(prim[l]==k) {g<<l; break;}
       }
    f.close();
    g.close();
    return 0;
}