#include <fstream>
#define Nmax 40
using namespace std;
ifstream f("damesah.in"); ofstream g("damesah.out");

int N,sol,gasit,st[Nmax],lin[Nmax],col[Nmax],d1[Nmax],d2[Nmax];

#define d1 ( d1 + 20 )
#define d2 ( d2 + 20 )

void PrintSol()
{
     for(int i=1;i<=N;++i)g<<st[i]<<' ';
     g<<'\n';
     gasit=1;
}

void Back(int i)
{
     if(i>N)
     {
          if(!gasit)PrintSol();
          ++sol;
          return;
     }
     for(int j=1;j<=N;++j)
          if(!col[j] && !d1[j-i] && !d2[N+1-j-i])
          {
               st[i]=j; col[j]=d1[j-i]=d2[N+1-j-i]=1;
               Back(i+1);
               col[j]=d1[j-i]=d2[N+1-j-i]=0;
          }
}

int main()
{
     f>>N;
     Back(1);
     g<<sol<<'\n';
     return 0;
}