#include<fstream>
using namespace std;
char s[1000009];
int main(){
  int i, j, n, k,t,c;
  s[1]=0;s[2]=s[3]=1;
  for(i=4;i<=1000000;i++){
    c=i;
    if(c%2==0){
      while(c%2==0)  c>>=1;
      if(s[c]>9)  s[i]=s[c];
      else s[i]=1+s[c];
    }
    else {
      for(j=3;j*j<=c;j++)
        if(c%j==0){
          while(c%j==0)  c/=j;
          if(s[c]>9)  s[i]=s[c];
          else s[i]=1+s[c];
        }
      if(!s[c])  s[c]=1;
    }
  }
  ifstream f("divprim.in");
  ofstream g("divprim.out");
  f>>t;
  for(i=0;i<t;i++){
    f>>n>>k;
    for(j=n;j>0;j--)
      if(s[j]==k){
        g<<j<<'\n';
        break;
      }
  }
  f.close();
  g.close();
  return 0;
}