#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int x[13],n,nr,ok=0;
void tipar()
{int i,j;
for(i=1;i<=n;i++)
   g<<x[i]<<" ";
   g<<endl;

ok=1;}
int ebun(int k)
{int i;
for(i=1;i<k;i++)
    if(x[i]==x[k] ||abs(i-k)==abs(x[i]-x[k]))
    return 0;
return 1;

}
void backtrack(int k)
{int i;
if(k==n+1)
    {if(ok==0)tipar();
    nr++;}
    else  for(i=1;i<=n;i++)
    {
        x[k]=i;
    if(ebun(k)) backtrack(k+1);

    }


}
int main()
{
   f>>n;
   backtrack(1);
  g <<nr;
}