#include <iostream>
#include <fstream>

using namespace std;

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

const int Nmax = 13;

int n, nr;
bool c[Nmax + 5], dp[3 * Nmax + 5], ds[3 * Nmax + 5];
int queen[Nmax + 5];

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

void Backtracking(int i){
    for (int j = 1; j <= n; j++){
        queen[i] = j;
        if (!c[j] && !dp[i - j + n] && !ds[i + j]){
            c[j] = dp[i - j + n] = ds[i + j] = 1;
            if (i == n){
                if (!nr)
                    Print();
                nr++;
            }
            else
                Backtracking(i + 1);
            c[j] = dp[i - j + n] = ds[i + j] = 0;
        }
    }
}

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