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

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

int st[100],n,k,sol,ok=1;

bool valid(int k)
{
    for(int i=1;i<k;i++) {
        if(st[k]==st[i])
        return 0;
        if(abs(st[k]-st[i])==k-i)
            return 0;
    }
    return 1;
}
void afisare(){
    if(ok==1) {
    for(int i=1;i<=n;i++)
        out<<st[i]<<" ";
    out<<'\n';
    }
}

void bt(int k){
    for(int i=1;i<=n;i++)
    {
        st[k]=i;
        if(valid(k)){

            if(k==n)
                {afisare();sol++;ok=0;}
        else
            bt(k+1);
        }
    }
}
int main(){
    in>>n;
    bt(1);
    out<<sol;
}