// Problema reginelor BKT.cpp : Defines the entry point for the console application.
//

#include <fstream>

using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");

struct dama
{
	int x, y;
} dame[15];

int config[15][15];
int nr_dame;
int nr_sol;

inline int Abs(int numar)
{
	return numar < 0 ? -numar : numar;
}

inline bool Can_Be_Put(int x, int y)
{
	for (int i = 1; i < x; i++)
	{
		if (x == dame[i].x  || y == dame[i].y)
			return false;
		if (Abs(x - dame[i].x) == Abs(y - dame[i].y))
			return false;
	}
	return true;
}

inline void Afisare()
{
	for (int i = 1; i <= nr_dame; i++)
	{
		for (int j = 1; j <= nr_dame; j++)
		{
			if (config[i][j] == 1)
                cout << j << " ";
		}
	}
	cout << "\n";
}

void BKT(int nivel)
{
		if (nivel > nr_dame)
		{
		    nr_sol++;
			if(nr_sol == 1) Afisare();
		}
		else
		{
			for (int i = 1; i <= nr_dame; i++)
			if (Can_Be_Put(nivel, i))
			{
				config[nivel][i] = 1;
				dame[nivel] = { nivel, i };
				BKT(nivel + 1);
				config[nivel][i] = 0;
				dame[nivel] = { 0, 0 };
			}
		}
}

int main()
{
	cin >> nr_dame;
	BKT(1);
	cout << nr_sol;
	return 0;
}