program elysian;
const
fin='dfs3.in';fout='dfs3.out';
var
sushu:set of byte;
n,i,count:longint;
used:array[1..50] of boolean;
ans:array[1..50] of integer;
f1,f2:text;

procedure init;
begin
sushu:=[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
assign(f1,fin);reset(f1);
readln(f1,n);
close(f1);
assign(f2,fout);rewrite(f2);
end;

procedure print;
var
i:integer;
begin
for i:=1 to n-1 do
write(f2,ans[i],' ');
writeln(f2,ans[n]);
inc(count);
end;

procedure dfs(x:integer);
var
num:longint;
begin
if x=n then begin print;exit;end;

for num:=1 to n do
   if used[num]=false then
     if (ans[x]+num) in sushu then
     begin
      ans[x+1]:=num;
      used[num]:=true;
      dfs(x+1);
      used[num]:=false;
     end;
end;




BEGIN
init;
for i:=1 to n do
begin
ans[1]:=i;
used[i]:=true;
dfs(1);
used[i]:=false;
end;
writeln(f2,count);
close(f2);
end.