#include <bits/stdc++.h>

#define NMAX 15

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int n;

int sol[NMAX]; //sol[i] = coloana in care va sta dama de pe linia i
int nrsol = 0;
int gasitsol = 0;

bool uz[NMAX];
//uz[i] = 1 daca pe coloana i este deja o regina

void bkt(int k);

void afisare();

int main()
{
    fin>>n;
    bkt(1);
    fout<<nrsol<<'\n';
    return 0;
}

void bkt(int k) //CAND APELAM BKT(K) sunt plasate regine pe liniile 1, 2, ..., k - 1
{
    int i, j;
    if (k == n + 1) //au fost completate n pozitii
    {
        if(gasitsol != 1) afisare(); //afisez doar prima sol (minim lexicografic
        nrsol++;
        gasitsol = 1;
    }
    else
        //plasez o regina pe linia k pe toate coloanele permise
        for(i = 1; i <= n; i++)
            if(uz[i] == 0)
            {
                //verific daca plasand o regina pe linia k si coloana i as fi pe aceeasi diagonala cu o regina deja plasata
                for(j = 1; j <= k - 1; j ++)
                    if(k - j == abs(sol[j] - i)) break;
                if(j == k)
                {
                    sol[k] = i;
                    uz[i] = 1;
                    bkt(k+1);
                    uz[i] = 0;
                }
            }
}

void afisare()
{
    for(int i = 1; i <= n; i++) fout<<sol[i]<<' ';
    fout<<'\n';
}