#include <cstdio>

using namespace std;

int n, col[17], dia1[17], dia2[17], a[17], tot;

inline int print()
{
	if (++tot > 3) return EOF;
	
	for (int i = 1; i <= n; ++i)
		cout << a[i] << " "; 
	cout << endl;
	
	return 0;
}

void dfs(int k)
{
	if (k > n) 
	{
		print();
	}
	
	for (int i = 1; i <= n; ++i)
	{
		if (!col[i] && !dia1[k + i] && !dia2[k - i + n])
		{
			col[i] = 1;
			dia1[k + i] = 1;
			dia2[k - i + n] = 1;
			
			a[k] = i;
			dfs(k + 1);
			a[k] = 0;
			
			col[i] = 0;
			dia1[k + i] = 0;
			dia2[k - i + n] = 0;
		}
	}
}

int main()
{
	cin >> n;
	
	dfs(1);
	
	cout << tot << endl;
	
	return 0;
}