program ooo;
type
aa=array[1..50] of longint;
var
a,ab:array[1..50] of longint;
b:array[1..50] of boolean;
c:array[1..2500,1..2500] of boolean;
i,j,k,l,n,m,max,sum:longint;

t:text;
function su(p,pp:longint):boolean;
var
i,j,k:longint;
f:boolean;
begin
su:=false;
for i:=2 to trunc(sqrt(p+pp))+1 do
 if (pp+p) mod i=0 then begin su:=true;exit;end;
end;

procedure oo(q,nm:longint);
var

i,j,k:longint;

begin
ab[nm]:=q;
if (nm=n) then
 begin inc(max);
for i:=1 to n-1 do
write(t,ab[i],' ');
writeln(t,ab[n]);exit;end;
j:=sum;
for i:=1 to n do
if (b[i]<>true) then
 if c[sum,i]=true then begin b[i]:=true;

  sum:=i;oo(i,nm+1);sum:=j;b[i]:=false; end

end;


begin

assign(t,'dfs3.in');
reset(t);
readln(t,n);
close(t);
for i:=1 to n do
 for j:=1 to n do
  if su(i,j)=false then
   begin
    c[i,j]:=true;
    c[j,i]:=true;
   end;
assign(t,'dfs3.out');
rewrite(t);
for i:=1 to n do
 begin
  fillchar(b,sizeof(b),false);
  fillchar(ab,sizeof(ab),0);
  b[i]:=true;
  sum:=i;

  oo(i,1);
 end;

write(t,max);


close(t);
end.