#include<stdlib.h>
#include<stdio.h>
int *sol;
int contor = 0;
int n;
FILE *fIn;
FILE *fOut;
int validare(int k,int *sol,int n)
{
	for (int i = 0; i < k; i++)
		if (sol[i] == sol[k] || abs(i - k) == abs(sol[i] - sol[k]))
			return 0;
	return 1;
}
void afisare(int *sol,int n)
{
	for (int i = 0; i < n; i++)
		fprintf(fOut, "%d ", sol[i]);
}
void dame(int k,int *sol)
{
	
	if (k == n)
	{
		if (contor == 0)
			afisare(sol,n);
		contor++;
	}
	for (int i = 1; i <=n; i++)
	{
		sol[k] = i;
		if (validare(k,sol,n))
			dame(k + 1,sol);
	}
}
void main()
{
	fIn = fopen("damesah.in", "r");
	fOut = fopen("damesah.out", "w");

	
	fscanf(fIn, "%d", &n);
	sol = (int*)malloc((n+1)*sizeof(int));
	dame(0,sol);
	free(sol);
	fprintf(fOut,"\n%d", contor);
	fclose(fOut);
	fclose(fIn);
}