#include <fstream>
#include <bitset>
#define DIM 15
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,nr,i;
int sol[DIM];
bool C[DIM],D1[4*DIM],D2[4*DIM];

void back(int k){
    if(k>n){
        //avem solutie
        if(!nr){
            for(i=1;i<k;i++)
                g<<sol[i]<<" ";
            g<<"\n";
        }
        nr++;
        return;
    }
    for(register int j=1;j<=n;j++){
        if(!C[j] && !D1[j+k] && !D2[j-k+n]){
            C[j]=D1[j+k]=D2[j-k+n]=true;
            sol[k]=j;
            back(k+1);
            C[j]=D1[j+k]=D2[j-k+n]=false;
        }
    }
}

int main(void){

    f>>n;
    back(1);
    g<<nr;
    return 0;
}