program dfs;
const
fin='dfs3.in';
fou='dfs3.out';
var
a:array[1..15]of longint;
b:array[1..30]of boolean;
num:array[1..15,1..15]of longint;
l:array[1..15]of longint;
deep,total,i,j,n:longint;
bo:boolean;
f1,f2:text;

procedure init;
begin
assign(f1,fin); assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n);
if n=0 then begin write(f2,0); close(f1); close(f2); halt; end;
if n=1 then
 begin writeln(f2,1); writeln(f2,1); close(f1); close(f2); halt; end;
for i:=2 to (n+n-1) do
 begin
  bo:=true;
  for j:=2 to trunc(sqrt(i)) do
  if i mod j =0 then bo:=false;
  if bo=true then b[i]:=true;
 end;
for i:=2 to (n+n-1) do
for j:=1 to n do
 if (i-j>0)and(b[i]=true)and(i-j<=n) then
  begin
   inc(l[j]); num[j,l[j]]:=i-j;
  end;
for i:=1 to n do b[i]:=false;
end;

procedure dfs(deep:longint);
var
p,k,i,j:longint;
begin
k:=a[deep-1];
for i:=1 to l[k] do
 begin
 p:=num[k,i];
 if b[p]=false then
  begin
   b[p]:=true;
   a[deep]:=p;
   if deep=n
    then begin
          inc(total);
          for j:=1 to (n-1) do
          write(f2,a[j],' '); writeln(f2,a[n]);
         end
    else dfs(deep+1);
   b[p]:=false;
  end;
 end;
end;

begin
 init;
for i:=1 to n do
begin
 a[1]:=i;
 b[i]:=true;
 dfs(2);
 b[i]:=false;
end;
write(f2,total);
close(f1); close(f2);
end.