#include<stdio.h>

#include<iostream>
#include<fstream>

using namespace std;

#define MAXN 13
int D[MAXN]; // dama c se afla pe coloana c si linia D[c]

bool L[MAXN]; // liniile ocupate
bool DG1[2*MAXN-1]; // diagonalele de tip slash ocupate
bool DG2[2*MAXN-1]; // diagonalele de tip backslash ocupate

int nbsol1,nbsol2;
int N;

void dameBB(int c){ // plasarea damei pe coloana c
	if(D[0]>=((N+1)/2)){
		printf("%d\n",2*nbsol1+nbsol2);
		exit(0);
	}

	if(c==N){ // afisarea solutiei descoperite
		if((nbsol1+nbsol2)==0){
			for(int i=0;i<N;i++) 
				printf("%d ",D[i]+1);
			printf("\n");
		}
		if(D[0]<(N/2)) 
			nbsol1++;
		else
			nbsol2++;
		return;
	}
	for(int r=0;r<N;r++){
		if(!L[r] && !DG1[r+c] && !DG2[r-c+N-1]){
			D[c]=r; // alegerea unei linii pentru dama c
			L[r]=true; DG1[r+c]=true; DG2[r-c+N-1]=true;
			dameBB(c+1);
			L[r]=false; DG1[r+c]=false; DG2[r-c+N-1]=false;
		}
	}
}

int main(){

	//ifstream input("cautbin.in");
	//ofstream output("cautbin.out",std::ios::out);

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

	scanf("%d",&N);
	//input >> N;

	dameBB(0);

	//printf("%d\n",nbsol);

	//input.close();
	//output.close();
	return 0;
}