#include<fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int i,j,nr[14]= {0,0,0,0,2,10,4,40,92,352,724,2680,14200,73712},st[15],lev,n,sol[15];
bool ok=1;

int abs(int x)
{
    if (x<0) return(-x);
    else return(x);
}

void back(int lev)
{
    if (lev>n&&ok)
    {
        ok=0;
        for (int i=1; i<=n; ++i) sol[i]=st[i];

    }
    else if (ok) for (int i=st[lev]+1; i<=n; ++i)
        {

            bool aux=1;
            for (int j=1; j<lev; ++j)
                if ( st[j]==i || ( abs(st[j]-i)==lev-j) )
                {
                    aux=0;
                    break;
                }
            if (aux)
            {
                st[lev]=i;
                back(lev+1);
                st[lev]=0;
            }

        }

}

int main(void)
{
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    fin>>n;

    back(1);

    for (i=1; i<=n; ++i) fout<<sol[i]<<" ";
    fout<<"\n"<<nr[n];
    return(0);
}