#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

FILE *read, *write;

int N;
int number_of_solutions = 0;
int queens[5000];

bool goodPosition()
{

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (i != j)
			{
				if (queens[i] == queens[j] || 
					(abs(j - i) == abs(queens[i] - queens[j])))
					return false;
			}

	return true;
}

void print()
{
	for (int i = 0; i < N; i++)
	{
		if (i != N - 1)
			fprintf(write, "%d ",  queens[i]);
		else 
		fprintf(write, "%d\n", queens[i]);
	}

}

void back(int step)
{
	if (step == N)
		return;

	for (int i = 1; i <= N; i++)	
	{	
		queens[step] = i;
			
		if (step == N - 1 && goodPosition() == true)
		{
			number_of_solutions ++;
			if (number_of_solutions == 1)
				print();
		}
		else
			back(step + 1);		
		
	}

}

int main()
{

	read = (FILE *) fopen("damesah.in", "r");
	write = (FILE *) fopen("damesah.out", "w");

	int dummy = fscanf(read, "%d", &N);
	back(0);

	fprintf(write, "%d\n", number_of_solutions);

	fclose(read);
	fclose(write);

	return 0;
}