#include<fstream>
using namespace std;
ifstream fi("checker.in");
ofstream fo("checker.out");
int a[30];
int n,o=0;
void queen(unsigned row,unsigned ld,unsigned lr,unsigned i);
void pr(int r);
int main()
{
	fi>>n;
	queen(0,0,0,0);
	fo<<o<<endl;
	return 0;
}
void queen(unsigned row,unsigned ld,unsigned rd,unsigned i)
{
	if(row==(1<<n)-1)
	{
		pr(i);
	}
	else
	{
		unsigned pos=~(row|ld|rd)&((1<<n)-1);
		while(pos!=0)
		{
			unsigned p=pos&(-pos);
			int s=0;
			unsigned pl=p;
			while(pl!=1)
			{
				s++;
				pl=pl>>1;
			}
			a[i]=s+1;
			pos=pos-p;
			queen(row+p,(ld+p)<<1,(rd+p)>>1,i+1);
		}
	}
}
void pr(int r)
{
	o++;
	if(o<=3)
	{
	    for(int i=0;i<=r-1;i++)
			if(i!=r-1)
		        fo<<a[i]<<" ";
			else
				fo<<a[i];
		fo<<endl;
	}
}