#include<bits/stdc++.h>
using namespace std;
int a[10],b[10];
int n,cnt,s=0;
bool check(int x,int y){
	for(int i = 1;i <= x;i++){
		if(a[i]==y)return false;
		if(i+a[i]==x+y)return false;
		if(i-a[i]==x-y)return false;
	}
	return true;
}
void dfs(int row){
	if(row==n+1){
		for(int i = 1;i <= n;i++){
			if(s>=18){
				break;
			}
			s++;
			cout<<a[i]<<" ";
		}
		if(s<18){
			cout<<endl;
		}		
		cnt++;
		return;
	}
	for(int i = 1;i <= n;i++){
		if(check(row,i)){
			a[row]=i;
			dfs(row+1);
			a[row]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<endl<<cnt;
	return 0;
}