#include <cstdio>

const int N = (int)1e7; // 10^7
int min_prime[N + 1]; // {0...}
int pn, p[N]; // p - primes, pn - number of primes 

// ALGORITHM --- B ---
void primes()
{
  // is[a] = 0 or 1
  // min_prime[a] = min x : x > 1, x | a
  // a is prime <=> min_prime[a] == a
  // ----------------------> a is not prime  
  // a = min_prime[a] * b
  // b = a / min_prime[a]
  // min_prime[b] >= min_prime[a]
  //
  // a = b * prime
  // b * {p[0] <= p[1] <= ... <= p[i] == min_prime[b]}

  for (int b = 2; b <= N; b++)
  {
    if (min_prime[b] == 0)
      min_prime[b] = b, p[pn++] = b;
    for (int i = 0; i < pn && p[i] <= min_prime[b] && b * p[i] <= N; i++)
      min_prime[b * p[i]] = p[i]; // a = b * p[i], p[i] = min_prime[a]
      // for every one "a" exactly one time 
  }
}

// x ---> while (x > 1) x /= min_prime[x];

int main()
{
  primes();
/*
  for (int i = 0; i < 100; i++)
    printf("%d ", p[i]);
  puts("");
*/
  int x = 3628800;
  while (x > 1) printf("%d %d\n", x, min_prime[x]), x /= min_prime[x];
  return 0;
}