#include<fstream>
#define N 15
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
ifstream f("sahdame.in");
ofstream g("sahdame.out");
int n,lin[N],col[N],m[N][N],OK,sol;
void back(int k)
{
	if(k>n)
	{
		sol++;
		if(OK)
			return;
		OK=1;
		FOR(i,1,n)
		g<<lin[i]<<" ";
		g<<"\n";
		return;
	}
	FOR(i,1,n)
	{
		if(!col[i]&&!m[k][i])
		{
			col[i]=1;
			for(int a=k,b=i;a<=n&&b<=n;a++,b++)
			m[a][b]++;
			for(int a=k,b=i;a&&b<=n;a--,b++)
			m[a][b]++;
			for(int a=k,b=i;a<=n&&b;a++,b--)
			m[a][b]++;
			for(int a=k,b=i;a&&b;a--,b--)
			m[a][b]++;
			lin[k]=i;
			
			back(k+1);
			
			col[i]=0;
			for(int a=k,b=i;a<=n&&b<=n;a++,b++)
			m[a][b]--;
			for(int a=k,b=i;a&&b<=n;a--,b++)
			m[a][b]--;
			for(int a=k,b=i;a<=n&&b;a++,b--)
			m[a][b]--;
			for(int a=k,b=i;a&&b;a--,b--)
			m[a][b]--;
		}
	}
}
int main()
{
	f>>n;
	back(1);
	g<<sol;
	return 0;
}