#include<fstream>
#include<cstring>
using namespace std;
bool c[31],i[41],r[31];
int n,ans,temp[15];
void dfs(int x) 
{
	for(int y=1;y<=n;y++)
		if (c[y+13] && i[y+x+13] &&r[y-x+13])
		{
			temp[x]=y;
			c[y+13]=false;
			i[y+x+13]=false;
			r[y-x+13]=false;
			if(x<n)
				dfs(x+1);
			else
			{
				if(ans<3)
				{
					for (int i=1;i<=n;i++)
						printf("%d ",temp[i]); 
					printf("\n"); 

				}
				ans++;
				if (ans>14244)
				{
					ans+=59467;
					return;
				}
			}
			c[y+13]=true;
			i[y+x+13]=true;
			r[y-x+13]=true;
		}
}
int main()

{
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);
	scanf("%d",&n);
	memset(c,true,sizeof(c));
	memset(i,true,sizeof(i));
	memset(r,true,sizeof(r));
	ans=0;
	dfs(1);
	printf("%d",ans);
   return 0;
}