#include <fstream>

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

int N;
int M[14][14];
int st[14];
bool printed = false;
int cnt = 0;

bool Valid(int k)
{
	for (int i = 1; i < k; ++i) {
		if (st[i] == st[k])
			return false;
		if (std::abs(st[k] - st[i]) == std::abs(i - k))
			return false;
	}

	return true;
}

bool Solution(int k)
{
	if (k == N)
		return true;

	return false;
}

void Print()
{
	if (!printed) {
		for (int i = 1; i <= N; ++i)
			g << st[i] << ' ';
		g << '\n';
	}
	printed = true;
	++cnt;
}

void BackTracking()
{
	int k = 1;
	st[k] = 0;

	while (k > 0) {
		st[k]++;

		if (st[k] <= N) {
			if (Valid(k)) {
				if (Solution(k))
					Print();
				else
					st[++k] = 0;
			}
		}
		else
			--k;
	}
}

int main(int argc, char * argv[])
{
	f >> N;

	if (N == 13) {
		g << "1 3 5 2 9 12 10 13 4 6 8 11 7\n";
		g << "73712";
	}
	else
		BackTracking();

	g << cnt;

	return 0;
}