program tz;
const max=50;
var
  s:array[3..99] of boolean;
  h:array[1..max,0..50] of integer;
  flag:array[1..max] of boolean;
  a:array[1..max] of integer;
  n:integer;f1,f2:text;
  tot:longint;
procedure init;
  var
    i,j:integer;
  begin
    assign(f1,'dfs3.in');reset(f1);
    assign(f2,'dfs3.out');rewrite(f2);
    readln(f1,n);

    for i:=3 to n+n-1 do begin
      s[i]:=true;j:=2;
      while s[i]and(j<=sqrt(i)) do
        if i mod j=0 then s[i]:=false
                     else inc(j);
    end;
    for i:=1 to n do
      for j:=1 to n do
        if (i<>j)and (s[i+j])
           then begin
             inc(h[i,0]);h[i,h[i,0]]:=j;
                end;
    fillchar(flag,sizeof(flag),true);
end;
procedure print;
  var
   i:integer;
   begin
     for i:=1 to n-1 do write(f2,a[i],' ');
     writeln(f2,a[n]);
   end;
procedure try(x,i:integer);
  var k:integer;
    begin
     for k:=1 to h[x,0] do
        begin
       if  flag[k]  then begin
         a[i]:=h[x,k];flag[a[i]]:=false;
       if i=n then begin
          inc(tot);print;
                    end
       else try(a[i],i+1);
      flag[a[i]]:=true;
                            end;
end;
end;
procedure main;
  var i:integer;
   begin
     init;
     for i:=1 to n do begin
     a[1]:=i;flag[i]:=false;
     try(i,2);
     flag[i]:=true;
   end;
  end;
begin
  main;
  writeln(f2,tot);
  close(f1);
  close(f2);
end.