#include <fstream>
#include <cmath>
using namespace std;
ifstream fi("damesah.in");
ofstream fo("damesah.out");
int n,prima,A[15],i,nrsol,COL[30],D1[30],D2[30];
void afisare()
{
    for(i=1;i<=n;i++)
        fo<<A[i]<<" ";
    fo<<'\n';
}
void backtrack(int k)
{
    int i,sol;
    if(k==n+1)
    {
        if(prima==1)
        {
            afisare();
            prima=0;
        }
        nrsol++;
    }
    else
    {
        for(i=1;i<=n;i++)
            if(!COL[i] && !D1[n+i-k] && !D2[i+k])
            {
                A[k]=i;
                COL[i]=D1[n+i-k]=D2[i+k]=1;
                backtrack(k+1);
                COL[i]=D1[n+i-k]=D2[i+k]=0;
            }
    }

}
int main()
{
    fi>>n;
    prima=1;
    backtrack(1);
    fo<<nrsol;
    fi.close();
    fo.close();
    return 0;
}