#include <bits/stdc++.h>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");


bool drst[27],stdr[29],col[15];
#define stdr (stdr+12)

int n,sol[15],nrsol;

bool valid(int k,int j)
{
     if(col[j]==0 && stdr[k-j]==0 &&
        drst[k+j]==0) return 1;

     return 0;
}

void afisare()
{
     for(int i=1;i<=n;i++)
          fout<<sol[i]<<' ';
     fout<<'\n';
}

void back(int k)
{
     for(int j=1;j<=n;j++)
     {
          sol[k]=j;
          if(valid(k,j))
          {
               col[j]=stdr[k-j]=drst[k+j]=1;
               if(k==n)
               {
                    nrsol++;
                    if(nrsol==1)
                         afisare();
               }
               else back(k+1);

              col[j]=stdr[k-j]=drst[k+j]=0;
          }
     }
}

int main()
{
     fin>>n;
     back(1);
     fout<<nrsol;
    return 0;
}