#include <fstream>

using namespace std;

int n;

int printed;
int matrix[16][16];
int vector[16];

fstream fout;

void Put(int level,int position)
{
    int l1 = level;
    int p1 = position;
    while (l1 < n)
    {
        if (matrix[l1][p1] < 0)
        {
            matrix[l1][p1] = level;
        }
        l1 += 1;
    }

    int l2 = level;
    int p2 = position;
    while ((l2 < n) && (p2 >= 0))
    {
        if (matrix[l2][p2] < 0)
        {
            matrix[l2][p2] = level;
        }
        l2 += 1;
        p2 -= 1;
    }

    int l3 = level;
    int p3 = position;
    while ((l3 < n) && (p3 < n))
    {
        if (matrix[l3][p3] < 0)
        {
            matrix[l3][p3] = level;
        }
        l3 += 1;
        p3 += 1;
    }
}

void Remove(int level,int position)
{
    int l1 = level;
    int p1 = position;
    while (l1 < n)
    {
        if (matrix[l1][p1] == level)
        {
            matrix[l1][p1] = -1;
        }
        l1 += 1;
    }

    int l2 = level;
    int p2 = position;
    while ((l2 < n) && (p2 >= 0))
    {
        if (matrix[l2][p2] == level)
        {
            matrix[l2][p2] = -1;
        }
        l2 += 1;
        p2 -= 1;
    }

    int l3 = level;
    int p3 = position;
    while ((l3 < n) && (p3 < n))
    {
        if (matrix[l3][p3] == level)
        {
            matrix[l3][p3] = -1;
        }
        l3 += 1;
        p3 += 1;
    }
}

void play(int level)
{
    if (level == n)
    {
        if (printed == 0)
        {
            for (int a = 0;a < n;a += 1)
            {
                fout << (vector[a] + 1) << " ";
            }
            fout << "\n";
        }
        printed += 1;
        return;
    }
    for (int a = 0;a < n;a += 1)
    {
        if (matrix[level][a] < 0)
        {
            vector[level] = a;
            Put(level,a);
            play(level + 1);
            Remove(level,a);
        }
    }
}

int main(void)
{
    fstream fin("damesah.in",ios::in);
    fout.open("damesah.out",ios::out);

    fin >> n;
    for (int a = 0;a < n;a += 1)
    {
        for (int b = 0;b < n;b += 1)
        {
            matrix[a][b] = -1;
        }
    }

    play(0);

    fout << printed << "\n";

    fin.close();
    fout.close();

    return 0;
}