program dfs3;
type
shuzu=array[1..1000]of integer;
shuzu2=array[1..50] of boolean;
shuzu1=array[1..100] of integer;
var
s:shuzu;
s1:shuzu1;
f:shuzu2;
i,j,n,m,k,a,b:integer;
c:longint;
f1,f2:text;
flag,flag1:boolean;
procedure print;
var
i,j:integer;
begin
inc(c);
for i:=1 to n do
begin
write(f2,s[i],' ');
end;
writeln(f2);
end;
procedure try(y:integer);
var
j,k,v:integer;
begin
if y>n then print
else
begin
for k:=1 to n do
begin
flag:=false;
for j:=1 to m do
if (s1[j]=k+s[y-1])and(f[k]=true) then begin flag:=true; break; end;
if flag then begin
f[k]:=false;
s[y]:=k;
try(y+1);
f[k]:=true;
end;
end;
end;
end;
begin
assign(f1,'dfs3.in');reset(f1);
assign(f2,'dfs3.out');rewrite(f2);
readln(f1,n);
c:=0; m:=3;s1[1]:=2;s1[2]:=3;
for i:=5 to 97 do
begin
flag:=true;
for j:=2 to trunc(sqrt(i)) do
if i mod j=0 then flag:=false;
if flag=true then begin s1[m]:=i;
m:=m+1; end;
end;
for i:=1 to n do
begin
for j:=1 to n do
f[j]:=true;
s[1]:=i;
f[i]:=false;
try(2);
end;
writeln(f2,c);
close(f2);
end.
rottenwood