program dame;
var x:array[1..100] of byte;
n,u:byte;
nrsol:word;
fi, fo:text;

procedure scriesol;
var i,j:byte;
begin
inc(nrsol);
if u=1 then begin
for i:=1 to n do begin
for j:=1 to n do if x[i]=j then write(fo,j,' ');
end;
u:=0;
end;
end;

function potcont(k:byte):boolean;
var i:byte;
atac:boolean;
begin
atac:=false;
for i:=1 to k-1 do
if(x[i]=x[k]) or (k-i=abs(x[k]-x[i])) then atac:=true;
potcont:=not atac;
end;

procedure back(k:byte);
var i:byte;
begin
for i:=1 to n do
begin
x[k]:=i;
if potcont(k) then
if k=n then begin scriesol end
else back(k+1);
end;
end;

begin
assign(fi,damesah.in); assign(fo, damesah.out);
reset(fi); rewrite(fo);
u:=1;
read(fi,n);
nrsol:=0;
back(1); writeln(fo);
writeln(fo,nrsol);
close(fi);Close(fo);
end.