#include<iostream>
#include<fstream>
#include<math.h>
#define max 14
using namespace std;

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

int valid(int k, int *v) {
	for (int i = 0; i < k; i++)
		if ((v[i] == v[k]) || (abs(v[k] - v[i]) == (k - i)))
			return 0;
	return 1;
}

void afisare(int n, int *v, int &counter) {
	if (counter == 1)
	{
		for (int i = 0; i < n; i++) {
			g << v[i]+1 << " ";
		}
	}
}

void bkt(int k, int n, int *v, int &counter) {
	for (int i = 0; i < n; i++)
	{
		v[k] = i;
		if (valid(k,v)) {
			if (k==n-1){
					counter++;
					afisare(n,v,counter);
				}
			else
				bkt(k + 1, n, v, counter);
		}
	}
}

int main()
{
	int n, v[max], counter=0;
	f >> n;
	bkt(0, n, v, counter);
	g << endl << counter;
	f.close();
	g.close();
	return 0;
}