program abc;

type
  mass2 = array[1..100000] of longword;

type
  mass = array [1..20] of int64;

type
  massE = array[1..1000000000] of boolean;

procedure element(var prime: massE);// Решето Эрастофена
var
  j: int64;
  i, n: integer;

begin
  n := 1000000000;
  for i := 1 to n do
    prime[i] := true;
  prime[1] := false;
  for i := 2 to n do
    if prime[i] then
      if int64(i) * i <= n then
      begin
        j := i * i;
        while j <= n do
        begin
          prime[j] := false;
          j := j + i;
        end;
      end;
end;

procedure alg(var prime: massE; var n: int64);// Ищем самое близкое простое к  заданному числу
var
  x, i: int64;
begin
  if prime[n] then
    writeln(n)
  else
  begin
    i := n;
    repeat
      dec(i);

    until(prime [i] and (n - i >= 2));
    write(i, ' ');
    x := n - i;
    alg(prime, x);    // Ищем для остатка
  end;
end;

procedure input(var t: byte; var a: mass);
var
  i: byte;
begin
  for i := 1 to t do
    readln(a[i]);
end;

procedure output(var prime: massE; var a: mass; var t: byte);
var
  i: byte;
begin
  for i := 1 to t do
    alg(prime, a[i]);
end;

var
  prime: massE;
  a: mass;
  T: byte;

begin
  element(prime);
  readln(t);
  input(t, a);
  output(prime, a, t);
end.