#include <bits/stdc++.h>

using namespace std;

int A[100][100],N,rs[100],k,nr;

bool check(int B[][100],int row,int col){
	
	int i,j;
	for (i=0;i<col;i++){
		if (B[row][i]) return 0;
	}
	for (i=row,j=col;i>=0&&j>=0;i--,j--){
		if (B[i][j]) return 0;
	}
	for (i=row,j=col;j>=0&&i<N;i++,j--){
		if (B[i][j]) return 0;
	}
	return 1;
	
}

bool back(int B[][100], int lvl){
	if (lvl >=N){
		//cout <<"solution "<<endl;
		// for (int i=0;i<N;i++)
	//	for (int j=0;j<N;j++) cout <<A[i][j]<<" \n"[j==(N-1)];
		if (nr==0) {
			for (int i=N-1;i>=0;i--)
			for (int j=0;j<N;j++) if (A[i][j]) rs[++k]=j+1;
		}
		nr++;
	
	}
	for (int i=0;i<N;i++){
		if (check(B,i,lvl)){
			B[i][lvl]=1;
			if (back(B,lvl+1)) return 1;
			B[i][lvl]=0;
			
		}
		
	}
	
	return 0;
}

int main(){
	ifstream cin("dame.in");
	ofstream cout("dame.out");
	cin >>N;
	back(A,0);
	
		for (int i=1;i<=k;i++) cout <<rs[i]<<" ";
		cout <<endl;
		cout <<nr;
		
	
	
	return 0;
}