#include<fstream>
using namespace std;
int sol[100], nr;
int n;

ifstream f("damesah.in");
ofstream g("damesah.out");

void tipar()
{
	
	for (int i = 1; i <= n; i++)
		g << sol[i] << " ";
	g << endl;
}
bool isValid(int k)
{
	for (int i = 1; i < k; i++)
		if (abs(k - i) == abs(sol[k] - sol[i])||sol[i]==sol[k])
			return false;
	return true;
}

void back(int k)
{
	for (int i = 1; i <= n; i++)
	{
		sol[k] = i;
		if (isValid(k))
			if (k == n )
			{
				nr++;
				if(nr==1)
					tipar();
			}
			else
				back(k + 1);
	}
}

int main()
{
	f >> n;
	back(1);
	g << nr;
}