#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int sol[20], cont;
bool col[20], diag_p[35], diag_s[20];

void afis(){

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

void backt(int k){

    if(k == n + 1){
        if(cont==0)
            afis();
        else
            ++cont;
    }
    else
        for(int i = 1; i <= n; ++i)
            if(!col[i] && !diag_p[k-i+15] && !diag_s[k+i]){
                col[i] = diag_p[k-i+15] = diag_s[k+i] = 1;
                sol[k] = i;
                backt(k+1);
                col[i] = diag_p[k-i+15] = diag_s[k+i] = 0;
            }
}

int main()
{
    fin >> n;

    backt(1);

    fout << cont;

    return 0;
}