#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
const int N=15;
int n, lin[N], col[N], diag1[3*N], diag2[3*N], cnt;

void afis()
{
    if(cnt)
    {
        cnt++;
        return;
    }
    cnt=1;
    for(int i=1; i<=n; ++i)
        g<<lin[i]<<" ";
    g<<'\n';

}
void bkt(int k)
{
    for(int i=1; i<=n; i++)
    {
        lin[k]=i;
        if(!col[i] && !diag1[i-k+n] && !diag2[i+k])//VALIDARE
        {
            if(k==n)//SOLUTIE
                afis();
            col[i]=1;
            diag1[i-k+n]=1;
            diag2[i+k]=1;

            bkt(k+1);

            col[i]=0;
            diag1[i-k+n]=0;
            diag2[i+k]=0;
        }
    }
}
int main()
{
    f>>n;
    bkt(1);
    g<<cnt;
    return 0;
}