#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

struct NK
{ int  m_N;
  int  m_K;
}
;

struct X8
{ int  m_a[8];
}
;

bool
solveDivprim
()
{ bool  ok;
  
  ::std::ifstream  is("divprim.in");
  
  ::std::size_t  T;
  is >> T;
  
  // Întrebări.
  ::std::vector < NK >  Q(T);
  ::std::size_t  i;
  ::std::size_t  N;
  ::std::size_t  K;
  ::std::size_t  maxN = 1;
  for(i=0; T>i; ++i)
  { is >> N >> K;
    ok = (7 >=K);
    if( !ok)
    { ::std::cerr << "Invalid input.";
      ::std::cerr << ::std::endl;
      return false; // Failure.
    }
    Q.at(i).m_N = N;
    Q.at(i).m_K = K;
    maxN = ::std::max(maxN, N);
  }
  
  // Ciurul lui Erastotene.
  ::std::vector < int >  S(maxN, 0);
  S.push_back(0);
  ::std::size_t  s;
  for(i=2; maxN >= i; ++i)
  { if(0 == S.at(i)  )
    { for(s = i; maxN >= s; s += i)
      { S.at(s) = i;
      }
    }
  }
  
  // Programare dinamică.
  ::std::size_t  p;
  for(i=2; maxN >=i; ++i)
  { p = S.at(i);
    s = i;
    while (0 == (s % p)  )
    { s /= p;
    }
    S.at(i) = 1 + S.at(s);
  }
  
  // Preprocesare.
  X8  h;
  for(i=1; 7>=i; ++i)
  { h.m_a[i] = 0;
  }
  ::std::vector < X8 >  X(maxN);
  X.push_back(h);
  X.at(1) = h;
  ::std::size_t  k;
  for(i=2; maxN >=i; ++i)
  { k = S.at(i);
    h.m_a[k] = i;
    X.at(i) = h;
  }
  
  // Răspunsuri.
  ::std::ofstream  os("divprim.out");
  ::std::size_t  x;
  for(i=0; T>i; ++i)
  { NK  & r = Q.at(i);
    N = r.m_N;
    K = r.m_K;
    x = X.at(N).m_a[K];
    os << x << '\n';
  }
  
  return true; // Success.
}

int
main
()
{ int  status;
  try
  { bool  const ok = solveDivprim();
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2;
  }
  return status;
}