#include <bits/stdc++.h>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");
int v[15],n,nrSol;
bool OK=true;
bool Verif(int poz)
{
    for(int i=1; i<poz; i++)
        if(v[i]==v[poz]||abs(v[i]-v[poz])==abs(i-poz))
            return false;
    return true;
}
void Bkt(int poz)
{
    if(poz==n+1)
    {
        if(OK)
        {
            for(int i=1; i<=n; i++)
                g<<v[i]<<' ';
            OK=false;
        }
        nrSol++;

    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            v[poz]=i;
            if(Verif(poz))
                Bkt(poz+1);
        }
    }
}
int main()
{
    f>>n;
    Bkt(1);
    g<<'\n';
    g<<nrSol;
    return 0;
}