#include <iostream>
#include <fstream>

using namespace std;

int a[15][15], n, ok, cnt, k, v[15], diag1[30], diag2[30];

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

void bk(int i, int j)
    {
        if(i>n)
        {
            if(cnt == n)
            {
                k++;
                if(ok == 0)
                {
                    for(i=1; i<=n; i++)
                        for(j=1; j<=n; j++)
                            if(a[i][j] == 1)
                                g<<j<<" ";
                    ok = 1;
                }
            }
            return;
        }

        if(j>n)
        {
            j = 1;
            bk(i+1, j);
            return;
        }
        if(v[j] == 0 && diag1[n-j+i] == 0 && diag2[i+j+1] == 0)
        {
            a[i][j] = 1;
            v[j] = 1;
            diag1[n-j+i] = 1;
            diag2[i+j+1] = 1;
            cnt++;
            bk(i+1, 1);
            v[j] = 0;
            a[i][j] = 0;
            diag1[n-j+i] = 0;
            diag2[i+j+1] = 0;
            cnt--;
        }
        bk(i, j+1);
    }


int main()
{
    f>>n;
    bk(1, 1);
    g<<endl;
    g<<k;
    return 0;
}