#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

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

#define NMax 15

int n;
int c[NMax];
int nrsol;

void plaseaza(int);
void afisare();

int main(){
	fin >> n;
	plaseaza(0);
	fout << '\n' << nrsol;
}

void plaseaza(int k){
	int i, j, ok;
	if(k >= n){
		nrsol++;
		if(nrsol == 1) afisare();
	}
	else
		for(i = 0; i < n; i++){
			for(j = 0, ok = 1; j < k; j++)
				if(c[j] == i || k - j == abs(i - c[j])) ok = 0;
			if(ok){
				c[k] = i;
				plaseaza(k + 1);
			}
		}
}

void afisare(){
	int i;
	for(i = 0; i < n; i++)
		fout << c[i] + 1 << ' ';
}