#include <iostream>
#include <fstream>
int c[1000001];
using namespace std;

int main()
{   int n,t,i,d,j,k;
    fstream in("divprim.in");
    ofstream out("divprim.out");
    in>>t;
    for(i=2;i*i<=1000000;i++)
      if(c[i] == 0)
        for(d=i;d<=1000000;d+=i)
          c[d]++;
    for(i=0;i<t;i++){
      in>>n>>k;
      c[0]=k;
      j=n;
      while(c[j] != k)
        j--;
      out<<j<<"\n";
    }
    return 0;
}