#include <iostream>

using namespace std;
int n,nrSol=0,bestSol[11];
struct pozitie
{
    int l;
    int c;
};
pozitie x[12];
bool gasit=0;
int modul(int x)
{
    if(x<0)
        return -x;
    return x;
}
bool valid(int k)
{
    int i;
    for(i=1; i<k; i++)
        if(x[i].l==x[k].l||x[i].c==x[k].c||(modul(x[k].l-x[i].l)==modul(x[k].c-x[i].c)))
            return 0;
    return 1;
}
void salvare()
{
    int i,j;
    bool deModificat=0;
    int currSol[11]= {0};
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(x[j].l==i)
                currSol[i]=x[j].c;
    if(nrSol==0)
    {
        for(i=1; i<=n; i++)
            bestSol[i]=currSol[i];
    }
    else
    {
        for(i=1; i<=n; i++)
            if(bestSol[i]<currSol[i])
                break;
            else if(bestSol[i]>currSol[i])
                deModificat=1;
        if(deModificat)
            for(i=1; i<=n; i++)
                bestSol[i]=currSol[i];
    }
}
void gen(int k)
{
    if(gasit)
        return;
    if(k>n)
    {
        salvare();
        nrSol++;
    }
    else
    {
        for(int i=x[k-1].l+1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                x[k].l=i;
                x[k].c=j;
                if(valid(k))
                    gen(k+1);
            }
    }
}
int main()
{
    int i;
    x[0].l=0;
    x[0].c=0;
    cin>>n;
    gen(1);
    for(i=1;i<=n;i++)
        cout<<bestSol[i]<<' ';
    cout<<'\n'<<nrSol;

}