#include <iostream>
#include <fstream>
using namespace std;
int n,x[200],f[200],f2[200],s[200],sol;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
void afis(int k){
    if(sol==0){
        for(int i=1;i<=k;i++)
            fout<<x[i]<<" ";
        fout<<"\n";
    }
}
bool verif(int k,int i){
    if(f[x[k]]==1 ||f2[k-i+100]==1||s[k+i]==1)
        return false;
    if(k<=n)
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i){
        x[k]=i;
        if(verif(k,i)){
            f[x[k]]=1;
            f2[k-i+100]=1;
            s[k+i]=1;
        //    if(k==n && sol>0)
           //     sol++;
            if(k==n){
                afis(k);
                sol++;
            }
            back(k+1);
            f[x[k]]=0;
            s[k+i]=0;
            f2[k-i+100]=0;
        }

    }
}
int main (){

    fin>>n;
    back(1);
    fout<<sol;
    return 0;
}