#include<stdlib.h>
#include<stdio.h>


int n, *v,nr=0;

FILE *f = fopen("damesah.in", "r");
FILE *g = fopen("damesah.out", "w");



void citire()
{
	
	fscanf(f, "%d", &n);
	v = (int*)malloc((n + 1)*sizeof(int));

}




bool valid(int k, int q)
{
	
	for (int j = 1; j < k; j++)
	{
		if (     abs(k - j)  ==  (q - v[j]) )
			return 0;
	
		
		if ( v[j] == q ) 
			return 0;


	
		 
	}
	



	return 1;
}




bool valid2( int k)
{
	for (int i = 1; i < k - 1;i++)
	if (v[i] - i == v[i + 1] - i + 1) return 0;
	return 1;
}





void afisare()
{
	for (int i = 1; i <= n; i++)
		fprintf(g,"%d ", v[i]);
	fprintf(g,"\n");
}


void BT(int k)
{
	if (k == n+1)
	{
		if (valid2(k))
		{
			if (!nr)
				afisare(); 
			nr++;
		
		}
		
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			v[k] = i;
			if (valid(k,i))
			{	
				
				k++;
				
				BT(k);
				k--;
			}
			

		
		}
		
	}
}














int main()
{
	citire();
	BT(1);
	fprintf(g,"%d", nr);
	return 0;
}