#include <fstream>
#include <iostream>
#include <math.h>

using namespace std;
int n,a[30],c[15],d1[15],d2[15],nrsol,vv=1;
ifstream in ("damesah.in");
ofstream out ("damesah.out");

void afis()
{
    int i,j;

    for(i=0;i<n;i++)
    {out<<a[i]<<" ";

    }
    out<<'\n';
}

void reg(int l)
{int i,j,ok;

        if(n!=l)
        for (int i=1;i<=n;i++)
        {
        if (c[i]==0 && d1[i-l+n]==0 && d2[2*n-l-i+1]==0)
        {
            c[i]=d1[i-l+n]=d2[2*n-l-i+1]=1;
            a[l]=i;

            reg(l+1);
            c[i]=d1[i-l+n]=d2[2*n-l-i+1]=0;
        }
    }
 else{ ++nrsol;if (vv) afis(),vv=0;}
}
int main()
{int h;
in>>n;
reg(0);
out<<nrsol<<'\n';
    return 0;


}