program dfs3;

var n,i:integer;
    ans:longint;
    s:array[1..50]of integer;
    f:array[1..50]of boolean;
    txt:text;

procedure output;
 var i:integer;
 begin
  for i:=1 to n do
   write(txt,s[i],' ');
  writeln(txt);
 end;

function prime:boolean;
 var tmp,i,j:integer;
 begin
  prime:=true;

  for i:=1 to n-1 do
  begin
   tmp:=s[i]+s[i+1];

   if not(odd(tmp)) then
   begin
    prime:=false;
    exit;
   end;

   for j:=3 to trunc(sqrt(tmp)) do
    if odd(j) then
     if tmp mod j=0 then
     begin
      prime:=false;
      exit;
     end;
  end;
 end;

procedure search(a:integer);
 var p:boolean;
     i:integer;
 begin
  if a<=n then
   for i:=1 to n do
   begin
    if not(f[i]) then
    begin
     s[a]:=i;
     f[i]:=true;
     search(a+1);
     f[i]:=false;
    end;
   end else
    if prime then
    begin
     output;
     inc(ans);
    end;
 end;

begin
 assign(txt,'dfs3.in');
 reset(txt);
 readln(txt,n);
 close(txt);

 assign(txt,'dfs3.out');
 rewrite(txt);
 search(1);
 writeln(txt,ans);
 close(txt);
end.