VAR
x:ARRAY[1..nmax] OF integer;
a:ARRAY[1..nmax] OF boolean;
b:ARRAY[2..nmax*2] OF boolean;
c:ARRAY[-nmax..nmax] OF boolean;
count,n:integer;
PROCEDURE print;
VAR
k:integer;
BEGIN
count:=count+1;
FOR k:= 1 TO n DO
write(x[k]:4);
writeln;
END;
PROCEDURE try(i:integer);
VAR
j:integer;
BEGIN
FOR j:= 1 TO n DO
IF a[j] AND b[i+j] and c[i-j]
THEN BEGIN
x[i]:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
IF i<n
THEN try(i+1)
ELSE print;
a[j]:=true;
b[i+j]:=true;
c[i-j]:=true;
END{if}
END;
BEGIN
assign(input,'nqueen.in');
reset(input);
assign(output,'nqueen.out');
rewrite(output);
readln(n);
count:=0;
fillchar(a,sizeof(a),true);
fillchar(b,sizeof(b),true);
fillchar(c,sizeof(c),true);
try(1);
writeln(count);
close(input);
close(output);
END.