{Compiles in Free Pascal for Windows and probably other operating systems}
program a193429;
uses Crt;
const
  {lookup table of primes}
  prime: array[1..31] of integer = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,
    47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127);
var
  fact, fact2: array[0..31] of integer;
  m: array[1..128, 0..6] of integer;
  flist: array[1..64] of integer;
  reqf: array[1..128] of integer;
  maxprime, maxf, flistnum, tot, tot2: integer;
  f, i, j, k, n, x: integer;
  sol: boolean;

procedure init;
begin
  for i := 0 to 31 do
    fact[i] := 0;
  fact[0] := 1; fact[1] := 1;
  tot := 1;
  for i := 0 to 31 do
    fact2[i] := 0;
  tot2 := 0;
  for i := 1 to 128 do
    reqf[i] := 0;
  for i := 1 to 128 do
  begin
    for j := 0 to 6 do
      m[i, j] := 0;
    if i > 1 then
    begin
      x := i;
      j := 0; k := 0;
      repeat
        inc(j);
        if x mod prime[j] = 0 then
        begin
          inc(k);
          m[i, k] := j;
          inc(k);
          repeat
            x := x div prime[j];
            inc(m[i, k]);
          until x mod prime[j] > 0;
        end;
      until x = 1;
      m[i, 0] := k;
    end;
  end;
  for i := 1 to 64 do
    flist[i] := 0;
end;

procedure setnextfactorial;
begin
  i := 0;
  repeat
    inc(i, 2);
    inc(fact[m[n, i-1]], m[n, i]);
    inc(tot, m[n, i]);
  until i = m[n, 0];
  if m[n, i - 1] > fact[0] then fact[0] := m[n, i - 1];
end;

procedure setreqf;
begin
  i:=0;
  repeat
    inc(i);
    if (prime[i] <= n) and (2 * prime[i] > n) and (2 * prime[i] <= maxf) and (3 * prime[i] > maxf) then
      reqf[2 * prime[i]]:=1 else reqf[2 * prime[i]]:=0;
  until prime[i] >= n;
end;

function chkfactors(q: integer): boolean;
var
  chk: boolean;
begin
  chk := true;
  i := 0;
  repeat
    inc(i, 2);
    if m[q, i] + fact2[m[q, i - 1]] > fact[m[q, i - 1]] then chk:=false;
  until (i = m[q, 0]) or (chk = false);
  chkfactors:=chk;
end;

procedure addfactors(q: integer);
begin
  inc(flistnum);
  flist[flistnum] := q;
  i := 0;
  repeat
    inc(i, 2);
    inc(fact2[m[q, i - 1]], m[q, i]);
    inc(tot2, m[q, i]);
  until i = m[q, 0];
end;

procedure subfactors(q: integer);
begin
  i:=0;
  repeat
    inc(i, 2);
    dec(fact2[m[q, i - 1]], m[q, i]);
    dec(tot2, m[q, i]);
  until i = m[q, 0];
  flist[flistnum] := 0;
  dec(flistnum);
end;

procedure nextstep;
begin
  if (tot2 < tot) then
  begin
    f := flist[flistnum];
    repeat
      dec(f);
      if f > n then
      begin
        if chkfactors(f) = true then
        begin
          addfactors(f);
          if sol = false then nextstep;
          f := flist[flistnum];
          subfactors(f);
          if reqf[f] = 1 then f := n;
        end;
      end;
    until f = n;
  end else
  begin
    sol:=true;
    writeln(n, ' ', maxf);
  end;
end;

begin
  init;
  writeln(0, ' ', 1);
  writeln(1, ' ', 0);
  writeln(2, ' ', 0);
  n := 2;
  repeat
    inc(n);
    sol := false;
    setnextfactorial;
    maxprime := prime[fact[0]];
    maxf := (2 * maxprime) - 1;
    flistnum := 0;
    repeat
      inc(maxf);
      setreqf;
      f:=maxf;
      if chkfactors(f) = true then
      begin
        addfactors(f);
        nextstep;
        f := flist[flistnum];
        subfactors(f);
      end;
    until sol = true;
  until n = 62;
end.