#include <iostream>
using namespace std;
int h[105],l[105],z[105],y[105];//行列左右
int cnt,a;
int L(){
	if(cnt<3){
		for(int i=1;i<=a;i++){
			cout<<h[i]<<' ';
		}
		cout<<'\n';
	}
	cnt++;
}
void _print_(int x){
	if(x>a){
		L();
		return;
	}
	else for(int j=1;j<=a;j++){
		if(l[j]==0&&z[x+j]==0&&y[x-j+a]==0){
			h[j]=j;
			l[j]=1;
			z[x+j]=1;
			y[x-j+a]=1;
			_print_(x+1);
			l[j]=0;
			z[x+j]=0;
			y[x-j+a]=0;
		}
	}
}
int main(){
	cin>>a;
	_print_(1);
	cout<<cnt;
	return 0;
}