//Problem : Noip;
//Author  : CaiXinXiao;
//Way     : Search;
//Date    : 09-18

Program Dfs;
Const
  Su    : Array[1..10] of Longint=(2,3,5,7,11,13,17,19,23,29);
  MaxN  = 1000;
  Inf   = 'dfs3.in';
  Ouf   = 'dfs3.out';
Var
  Value : Array[1..MaxN] of Longint;
  SFlag : Array[1..30]   of Boolean;
  Flag  : Array[1..MaxN] of Boolean;
  n     : Longint;
  k     : Longint;

Procedure Init;
  Var
    r:Longint;
  Begin
    assign(input,Inf); reset(input);
    assign(output,Ouf); rewrite(output);
    FillChar(Value,sizeof(Value),0);
    FillChar(Flag,sizeof(Flag),True);
    FillChar(Sflag,sizeof(Sflag),False);
    Readln(n);
    For r:=1 to 10 do
      Sflag[Su[r]]:=True;
  End;

Procedure Print;
  Var
    r:Longint;
  Begin
    For r:=1 to n do
      write(Value[r],' ');
    writeln;
    Inc(k,1);
  End;

Procedure Search(Dep:Longint);
  Var
    r:Longint;
  Begin
    if dep > n then Print
    Else
    Begin
      For r:=1 to n do
        Begin
          if (Dep = 1) or ((Flag[r] <> False) and (Sflag[Value[dep-1]+r]=True)) then
            Begin
              Flag[r]:=False;
              Value[dep]:=r;
              Search(Dep+1);
              Flag[r]:=True;
            End;
        End;
    End;
  End;

Procedure Eend;
  Begin
    writeln(K);
    close(input);
    close(output);
  End;

BEGIN
  Init;
  Search(1);
  Eend;
END.