#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");
int v[15], n, solutii;

int verificare(int x, int y)
{
	int i, d1, d2;

	for(i=1; i<x; i++)
	{
		d1 = abs(x - i);
		d2 = abs(y - v[i]);

		if(v[i] == y || d1 == d2)
			return 0;
	}

	return 1;
}

void rezolvare(int regine)
{
	int i, j;

	if(regine < n)
	{
		i = regine + 1;

		for(j = 1; j<=n; j++)
		{
			if(verificare(i, j) == 1)
			{
				v[i] = j;
				rezolvare(regine + 1);
				v[i] = 0;
			}
		}
	}
	else
	{
		solutii++;

		if(solutii == 1)
		{
			for(i=1; i<=n; i++)
				g << v[i] << ' ';

			g << endl;
		}
	}
}

int main()
{
	f >> n;
	solutii = 0;

	rezolvare(0);

	g << solutii;

	f.close();
	g.close();
	return 0;
}