#include<stdio.h>
#include<math.h>
FILE *input, *output;
struct REGINA {
	int linie;
	int coloana;
};
int n, cntSol = 0;
bool primaSolAfisata = false;
REGINA stiva[15];
void afiseazaSolutia()
{
	if (primaSolAfisata == true) return;

	primaSolAfisata = true;
	for (int i = 1; i <= n; i++)
		fprintf(output, "%d ", stiva[i].coloana);
}
bool pozitieValida(int coloana, int nivel)
{
	for (int i = 1; i < nivel; i++)
		if (stiva[i].coloana == coloana || abs(stiva[i].linie - nivel) == abs(stiva[i].coloana - coloana))
			return false;

	return true;
}
void BKT(int nivel)
{
	if (nivel == n)
	{
		cntSol++;
		afiseazaSolutia();
		return;
	}

	nivel++;
	for (int coloana = 1; coloana <= n; coloana++)
		if (pozitieValida(coloana, nivel))
		{
			stiva[nivel].linie = nivel;
			stiva[nivel].coloana = coloana;
			BKT(nivel);
		}
}
int main()
{
	input = fopen("damesah.in", "r");
	output = fopen("damesah.out", "w");

	fscanf(input, "%d", &n);
	
	BKT(0);

	fprintf(output, "\n%d\n", cntSol);

	return 0;
}