#include <fstream>
#define MAX_N 13

using namespace std;

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


int v[MAX_N], n, s = 0;
bool u[MAX_N], d1[MAX_N * 2 + 1], d2[MAX_N * 2 + 1];

void bk(int k) {
	if (k < n) {
		for (int i = 0; i < n; ++i) {
			if (u[i] && d1[k + i] && d2[k - i + n]) {
				v[k] = i;
				u[i] = false;
				d1[k + i] = false;
				d2[k - i + n] = false;
				bk(k + 1);
				u[i] = true;
				d1[k + i] = true;
				d2[k - i + n] = true;
			}
		}
	}
	else {
		if (s++ == 0) {
			for (int i = 0; i < n; ++i) {
				fout << v[i] + 1 << " ";
			}
			fout << "\n";
		}
	}
}

int main() {
	fin >> n;
	for (int i = 0; i < n; ++i) {
		u[i] = true;
	}
	for (int i = 0; i <= MAX_N * 2; ++i) {
		d1[i] = true;
		d2[i] = true;
	}
	bk(0);
	fout << s;
	return 0;
}