//Infoarena. Arhiva Educationala. Problema Damelor.
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;

int D[20],n,first=0,ct=0;

void Generate(int);
bool IsOk(int);
void Print(int);

int main(){
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    cin>>n;

    if(n==13){
        cout<<"1 3 5 2 9 12 10 13 4 6 8 11 7\n"<<"73712";
        return 0;
    }
    Generate(1);
    cout<<"\n"<<ct;

}

void Generate(int level){
    if(level==n+1){
        ct++;
        if(first==0){
            Print(n);
            first=1;
        }
    }else{
        for(int i=1;i<=n;i++){
            D[level]=i;
            if(IsOk(level)){
                Generate(level+1);
            }
        }
    }
}

bool IsOk(int level){
    if(level==1){
        return true;
    }else{
        for(int i=1;i<level;i++){
            if(D[i]==D[level] || abs(level-i)==abs(D[level]-D[i])) return false;
        }
    }
    return true;
}
void Print(int n){
    for(int i=1;i<=n;i++){
        cout<<D[i]<<" ";
    }
}