//Drugescu Alexandru
//C.N.I Grigore Moisil
//Clasa XD
//[email protected]
#include <iostream>
#include <fstream>
using namespace std;
int n,p,d=2,pr=0,div,x,i;
int promp(int x,int div);

int main()
{
  while(x!=1)
  {
      if(x%d==0)
      {
          p++;
          if(pr>div)
            return 0;
          while(n%d==0)
            x/=d;
      }
      d++;
  }
  if(pr==div)
      return 0;
      return 0;
  }
  ifstream f("divprim.in")
  ofstream g("divprim.out")
  int n,i;
  f<<n;
  int a[2][n];
  for(int i=0;i<n;i++)
    f>>a[1][i] >>a[2][i];
      for(int i=0;i<n;i++)
      {
          int ok=1;
          while(ok && a[1][i]>0)
          {
              if(prop(a[1][i],a[2][i])==0)
                a[1][i]--;
              else
                ok=0;

          }
          g << a[1][i] << "\n"
      }






    return 0;
}