#include <fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,sol,ok,s[15][15];
int dx[]={1,-1,-1,1};
int dy[]={1,1,-1,-1};
bool in_matrice(int x,int y)
{
    return (x<=n && x>=1&& y<=n && y>=1);
}
int verif_coloana_diagonale(int linie,int coloana)
{
    int i,j;
    for (i=1; i<=n; ++i) /// verificare coloana
        if (i!=linie && s[i][coloana])
            return 0;
    for (int i=0;i<4;++i)
    {
        int nou_x=linie+dx[i],nou_y=coloana+dy[i];
        if (in_matrice(nou_x,nou_y) && s[nou_x][nou_y]) return 0;
    }
    return 1;
}
void dame(int lin)
{
    if (lin==n+1)
    {
        sol++;
        if (!ok)
        {
            for (int ii=1; ii<=n; ++ii)
            {
                for (int j=1; j<=n; ++j)
                {
                    if (s[ii][j])
                    {
                        out<<j<<" ";
                        break;
                    }
                }
            }
            ok=1;
        }
        return;
    }
    for (int ii=1; ii<=n; ++ii)
    {
        if (verif_coloana_diagonale(lin,ii))
        {
            s[lin][ii]=1;
            dame(lin+1);
            s[lin][ii]=0;
        }
    }
}
int main()
{
    in>>n;
    dame(1);
    out<<"\n"<<sol;
}