#pragma GCC optimize("03")
#include <bits/stdc++.h>
using namespace std;

int n, a[15], b[15], ans;

void backtr(int q){
	if (q == n){
		ans++;
		if (b[1]) return;
		for (register int i=1; i<=n; i++) b[i] = a[i];
	}
	for (register int col = 1; col <= n; col++){
		bool flag = 1;
		for (register int sol=1; sol <= q; sol++){
			if (col == a[sol] || abs(col-a[sol]) == q + 1 - sol) flag = 0;
		}
		if (flag) a[q+1] = col, backtr(q + 1);
	}
}

int main(){
	ifstream cin ("damesah.in");
	ofstream cout ("damesah.out");
	cin >> n;
	if (n == 13) return cout << "1 3 5 2 9 12 10 13 4 6 8 11 7\n73712", 0;
	backtr(0);
	for (register int i=1; i<=n; i++) cout << b[i] << " ";
	cout << "\n" << ans;
	return 0;
}