#include <bits/stdc++.h>
#define MAX 20

using namespace std;

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

int n,v[MAX],sol;
int valid(int k);
int solutie(int k);
bool p = true;

void afisare();

void BK(int k);

void BK(int k){
    int i;
    for (i=1;i<=n;i++){
        v[k]=i;
        if (valid(k)==1){
            if (solutie(k)==1){
                if (p) afisare(), p=false;
                sol++;
            }
            else
                BK(k+1);
        }
    }
}

int valid(int k){
    int i;
    for (i=1;i<=k-1;i++)
        if ((v[i]==v[k])||(abs(v[k]-v[i])==(k-i)))
            return 0;
    return 1;
}

int solutie(int k){
    if (k==n)
        return 1;
    return 0;
}

void afisare(){
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++)
            if (v[i]==j) out << j << " ";
    }
    out << "\n";
}

int main(){
    in>>n;
    BK(1);
    out << sol;
    return 1;
}