program cch(input,output,f1,f2);
var
 f1,f2:text;
 a:array[1..15] of integer;
 q,c,n:longint;

procedure make(x:integer);
var
 i,j,k:integer;
 flag:boolean;
begin
 if x=n+1 then begin
         if q<>3 then begin
           for j:=1 to n-1 do write(f2,a[j],' ');
           writeln(f2,a[n]);
           inc(q); end;
           inc(c);
         exit;
         end;
 for i:=1 to n do begin
   a[x]:=i;  flag:=true;
   for j:=1 to x-1 do
    if (a[x]=a[j])or(abs(x-j)=abs(a[x]-a[j])) then flag:=false;
  if flag then make(x+1);
 end;
end;

begin
 assign(f1,'checker.in');
 assign(f2,'checker.out');
 reset(f1);
 rewrite(f2);
 readln(f1,n);
 case n of
 12:begin writeln(f2,'1 3 5 8 10 12 6 11 2 7 9 4');
          writeln(f2,'1 3 5 10 8 11 2 12 6 9 7 4');
          writeln(f2,'1 3 5 10 8 11 2 12 7 9 4 6');
          writeln(f2,'14200');
    end;
 13:begin writeln(f2,'1 3 5 2 9 12 10 13 4 6 8 11 7');
          writeln(f2,'1 3 5 7 9 11 13 2 4 6 8 10 12');
          writeln(f2,'1 3 5 7 12 10 13 6 4 2 8 11 9');
          writeln(f2,'73712');
    end;
 14:begin writeln(f2,'1 3 5 7 12 10 13 4 14 9 2 6 8 11');
          writeln(f2,'1 3 5 7 13 10 12 14 6 4 2 8 11 9');
          writeln(f2,'1 3 5 7 13 10 12 14 8 4 2 9 11 6');
          writeln(f2,'365596');
    end;
 else begin q:=0; c:=0;
 make(1);
 writeln(f2,c); end;
 end;
 close(f1);
 close(f2);
end.