#include <iostream>
#include <cstdio>
#include <cmath>
#define Dmax 20
using namespace std;

int N; int C[Dmax]; int NR,NR_VARIANTE;

void PLASARE_REGINA(int);
void AFISARE(void);

void PLASARE_REGINA(int k)
{
    int i,j,okay;
    //cand apelam functia PLASARE_REGINA cu parametrul k, am plasat deja regine pe liniile 1,2,...,k
    if(k==N+1) AFISARE();  //am obtinut o solutie
    else
    {
        //trebuie sa mai plasam regine pe pozitiile k+1,k+2,...,N
        for(i=1; i<=N; i++)
        {
            //verific daca pot plasa regina de pe linia k pe coloana i
            for(okay=1, j=1; j<k; j++)
                if(C[j]==i || abs(k-j)==abs(C[j]-i)) okay=0; //regina s-ar gasi pe o aceeasi linie sau diagonala cu o regina deja plasata

            if(okay==1) //valoarea i respecta conditiile interne
            {
                C[k]=i; //i este un candidat, il extrag imediat
                PLASARE_REGINA(k+1);
            }
        }
    }
}

void AFISARE()
{
    if(NR<1)
    {
    for(int j=1; j<=N; j++) printf("%d ",C[j]);
    printf("\n");
    NR++;
    }
    NR_VARIANTE++;
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d",&N);

    PLASARE_REGINA(1);
    printf("%d",NR_VARIANTE);

    return 0;
}