program dfs3;
type jh=set of 1 .. 30;
const sushu:jh=[2,3,5,7,11,13,17,19,23,29];
var ddi,ddo:text;
n:longint;
x1,x2:longint;
pai:array[1..15] of integer;
nn:jh;
jg:longint;
t:longint;
procedure wri;
var x:integer;
begin
for x:=1 to n-1 do
write(ddo,pai[x],' ');
writeln(ddo,pai[n]);
jg:=jg+1;
end;
procedure go;
var x:integer;
begin
if t=1 then
for x:=1 to n do
begin
nn:=nn+[x];
pai[1]:=x;
t:=t+1;
go;
t:=t-1;
nn:=nn-[x];
end;
if t>1 then
for x:=1 to n do
if (not(x in nn)) and (x+pai[t-1] in sushu) then
begin
pai[t]:=x;
nn:=nn+[x];
if t<n then
begin
t:=t+1;
go;
t:=t-1;
end;
nn:=nn-[x];
if t=n then wri;
end;
end;
begin
assign(ddi,'dfs3.in');
reset(ddi);
readln(ddi,n);
close(ddi);
assign(ddo,'dfs3.out');
rewrite(ddo);
jg:=0;
nn:=[];
t:=1;
go;
writeln(ddo,jg);
close(ddo);
end.
NickName