#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;
int n,c[15],nrSol;
ifstream f("damesah.in");
ofstream g("damesah.out");
void afisare()
{

    for(int i=1;i<=n;i++)g<<c[i]<<" ";
}
void dama(int k)
{

    int i,j,ok;
    if(k==n+1){
    if(nrSol==0)afisare();

     nrSol++;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(ok=1,j=1;j<k;j++)
                if(c[j]==i||abs(c[j]-i)==abs(k-j))ok=0;
            if(ok==1)
            {
                c[k]=i;
                dama(k+1);
            }
        }
    }
}
int main()
{

    f>>n;
    dama(1);
    g<<"\n"<<nrSol;
    return 0;
}