#include <fstream>
using namespace std;

ifstream cin ("damesah.in");
ofstream cout ("damesah.out");

int lungime , tabla[14][14] , pozitii[14] , modalitati;

void Afisare ()
{
    for (int indice = 1 ; indice <= lungime ; indice++)
        cout << pozitii[indice] << ' ';
    cout << '\n';
}

bool Valid (int linie , int coloana)
{
    for (int indice = 1 ; indice < linie ; indice++)
        if (pozitii[indice] == coloana || abs(coloana - pozitii[indice]) == linie - indice)
            return false;

    return true;
}

void Backtracking (int linie)
{
    for (int coloana = 1 ; coloana <= lungime ; coloana++)
        if (Valid(linie , coloana))
        {
            pozitii[linie] = coloana;
            if (linie == lungime && ++modalitati == 1)
                Afisare();
            else
                if (linie < lungime)
                    Backtracking(linie + 1);
        }
}

int main ()
{
    cin >> lungime;
    Backtracking(1);
    cout << modalitati;
    cout.close(); cin.close();
    return 0;
}