#include <fstream>
using namespace std;
int n, sol[20], lin, ok, nr, ii;
int d2[40], d1[40], col[40];
ifstream fin("damesah.in");
ofstream fout("damesah.out");

void backt(int lin)
{
    if(lin>=n+1)
    {
        for(++ok, ii=0; ok<=1 && ii<n; fout<<sol[++ii]<<' ');
        return;
    }
    for(int i=1; i<=n; ++i)
        if(!d1[lin+i-1] && !d2[lin-i+n] && !col[i])
        {
            sol[lin]=i;
            d1[lin+i-1]=d2[lin-i+n]=col[i]=1;
            backt(lin+1);
            d1[lin+i-1]=d2[lin-i+n]=col[i]=0;
        }
}

int main()
{
    fin>>n;
    backt(1);
    fout<<'\n'<<ok;
    return 0;
}