#include <fstream>
#include <iostream>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int st[15];
int N, nb_sol = 0;

bool afiseaza_solutie = true;

void init(int k) {
	st[k] = 0;
}

bool successor(int k) {
	if (st[k] < N) {
		st[k]++;
		return true;
	}
	return false;
}

bool is_consistent(int k) {
	for (int i = 1; i < k; ++i) {
		if (st[k] == st[i] || abs(st[k] - st[i]) == k - i) {
			return false;
		}
	}
	return true;
}

bool is_solution(int k) {
	return k == N;
}

void output_solution(int k) {
	for (int i = 1; i <= N; ++i)
		g << st[i] << ' ';
	g << '\n';
}

void backtrack_rec(int k) {
	init(k);
	while (successor(k)) {
		if (is_consistent(k)) {
			if (is_solution(k)) {
				nb_sol++;
				if (afiseaza_solutie) {
					output_solution(k);
					afiseaza_solutie = false;
				}
				
			}
			else {
				backtrack_rec(k + 1);
			}
		}
	}
}

int main() {
	// input
	f >> N;
	f.close();

	// solve
	backtrack_rec(1);

	// output - number of solutions
	g << nb_sol << '\n';
	g.close();

	return 0;
}