// Day4V1.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int st[20], n,nrSol=0;
void afisare() {
	for (int i = 1; i <= n; ++i) {
		g << st[i] << " ";
	}
	g << "\n";
}
int valid(int k) {
	for (int i = 1; i < k; ++i) {
		if (st[k] == st[i] || abs(st[k]-st[i]) == abs(k-i))
			return 0;
	}
}
void BK(int k) {
	for (int i = 1; i <= n; ++i) {
		st[k] = i;
		if (valid(k)) {
			if (k == n) {
				++nrSol;
				if(nrSol == 1)
				afisare();
			}
			else
				BK(k + 1);
		}
	}
}
int main()
{
	f >> n;
	BK(1);
	g << nrSol << "\n";
    return 0;
}