program dfs;
var
 n,m,i,l:longint;
 f1,f2:text;
 a:array[1..100] of longint;
 b:array[1..100] of boolean;
function pd(x:longint):boolean;
var i:longint;
begin
 pd:=true;
 for i:=2 to trunc(sqrt(x)) do
 if x mod i =0 then begin
                     pd:=false;
                     exit;
                     end;
end;
procedure init;
var i:longint;
begin
 assign(f1,'dfs3.in');reset(f1);
 assign(f2,'dfs3.out');rewrite(f2);
 read(f1,n);
 m:=0;
end;
procedure from(y:longint);
var j:longint;k:longint;
begin
 for j:=1 to n do
 if b[j] then
 if pd(y+j) then
  begin l:=l+1;a[l]:=j;b[j]:=false;
         if l=n then begin
                        for k:=1 to n do write(f2,a[k],' ');
                        writeln(f2);
                        m:=m+1;
                        end
         else from(j);
       l:=l-1;b[j]:=true;
  end;
end;
begin
 init;
 for i:=1 to n do begin
  fillchar(b,sizeof(b),true);
  fillchar(a,sizeof(a),0);
  l:=1; a[l]:=i;b[i]:=false;;
  from(i);end;
 write(f2,m);
 close(F1);close(f2);
end.