#include <fstream>
#include <iostream>


using namespace std;

int N;
int number_of_solutions = 0;
int queens[20];
ifstream read("damesah.in");
ofstream write("damesah.out");

bool goodQueen(int step)
{

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

	return true;
}

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

	for (int i = 1; i <= N; i++)	
	{	
		queens[step] = i;
			
		if (goodQueen(step) == true)
		{
				if (step == N - 1)
				{
					number_of_solutions ++;
					if (number_of_solutions == 1)
					{
						for (int i = 0; i < N; i++)
						{
							if (i != N - 1)
								write << queens[i] << " ";
							else 
								write << queens[i] << "\n";
						}
					}
				}
				else
					back(step + 1);		
		}
	}

}

int main()
{

	read >> N;

	back(0);

	write << number_of_solutions << '\n';

	read.close();
	write.close();

	return 0;
}