#include<bits/stdc++.h>
using namespace std;

int a[1000],b[1000],c[1000],d[1000];
int times;
int n;

int print(){
	if(times<=2){
		for(int k = 1; k <= n; k++){
			cout<<a[k]<<" ";
		}
		cout<<endl;
	}
	times++;
}
void bfs(int i){
	if(i>n){
		print();
		return; 
	} 
	else{
		for(int j = 1; j<=n; j++){
			if((!b[j])&&(!c[j+i])&&(!d[i-j+n])){
				a[i] = j;
				b[j] = 1;
				c[i+j] = 1;
				d[i-j+n] = 1;
				bfs(i+1);
				b[j] = 0;
				c[i+j] = 0;
				d[i-j+n] = 0;
			}
		}
	}
}
int main(){
	cin>>n;
	bfs(1);
	cout<<times;
	return 0;
}