#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define SZ(a) (int)(a).size()

int n;
int ans;
int M0;
vector<int> queens;

bool dfs1(int M1, int M2, int M3) {
	if (M1 == M0) {
		for (int i = 0; i < n; i++) {
			printf("%d%c", __builtin_ctz(queens[i])+1, " \n"[i == n-1]);
		}
		return true;
	}
	else {
		bool flag = false;
		for (auto M = M0 ^ (M1 | M2 | M3); M && !flag; M &= M-1) {
			int B = M & -M;
			queens.push_back(B);
			flag |= dfs1(M1 | B, M0 & (M2 | B)<<1, M0 & (M3 | B)>>1);
			queens.pop_back();
		}
		return flag;
	}
}

void dfs(int M1, int M2, int M3) {
	if (M1 == M0) {
		if (ans++ == 0) {
		}
	}
	else {
		for (auto M = M0 ^ (M1 | M2 | M3); M; M &= M-1) {
			int B = M & -M;
			dfs(M1 | B, M0 & (M2 | B)<<1, M0 & (M3 | B)>>1);
		}
	}
}

void solve() {
	cin >> n;
	M0 = (1<<n)-1;
	ans = 0;
	dfs1(0, 0, 0);
	dfs(0, 0, 0);
	printf("%d\n", ans);
}

int main() {
#ifdef INFOARENA
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);
#endif
	cin.sync_with_stdio(false);
	solve();
	return 0;
}