#include <bits/stdc++.h>
using namespace std;

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

const int dim=15;

int n,sol[dim],ok,cnt;

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

bool verifica(int x,int pas){
    for(int i=1;i<pas;i++){
        if(sol[i]==x||abs(x-sol[i])==abs(pas-i)){
            return 0;
        }
    }
    return 1;
}

void backtracking(int pas){
    for(int i=1;i<=n;i++){
        if(verifica(i,pas)){
            sol[pas]=i;
            if(pas==n){
                afisare();
            }
            else{
                backtracking(pas+1);
            }
        }
    }
}

signed main(){
    fin>>n;
    backtracking(1);
    fout<<cnt;
}