#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

struct dame
{
    int x,y;
}aux;

dame a[15],s[15];
int n,nr;
bool first=true;

bool test(int x,int y,int m)
{
    for(int i=1; i<=m; i++)
        if (a[i].x==x || a[i].y==y || abs(a[i].x-x)==abs(a[i].y-y)) return false;
    return true;
}


void ins(int x, int y, int poz)
{
    aux.x=x;
    aux.y=y;
    a[poz]=aux;
    if (poz==n)
    {
        if(first)
        {
            first=false;
            for(int i=1; i<=n; i++)
                s[i]=a[i];
        }
        nr++;
    }else{

        for(int j=1; j<=n; j++)
            if (test(x+1,j,poz))
                ins(x+1,j,poz+1);

    }
}






void backtrack()
{
    for(int j=1; j<=n; j++)
        ins(1,j,1);
}


int main()
{

    f>>n;

    backtrack();

    for(int i=1; i<=n; i++)
        g<<s[i].y<<" ";

    g<<"\n"<<nr;

    return 0;
}