# include <stdio.h>
# define MAX	13

int N;
int numberOfSolutions = 0;
FILE *fin, *fout;

int solution[MAX];
bool usedColumn[MAX], usedMainDiag[2 * MAX - 1], usedSndDiag[2 * MAX - 1];

void printFirstSolution() {
	for (int i = 0; i < N; i++) {
		fprintf(fout, "%d ", solution[i]);
	}
	fprintf(fout, "\n");
}

bool isSafe(int row, int col) {
	return (!usedColumn[col])
		&& (!usedMainDiag[row - col + N - 1])
		&& (!usedSndDiag[row + col]);
}

void putQueen(int row, int col) {
	usedColumn[col]
		= usedMainDiag[row - col + N - 1]
		= usedSndDiag[row + col]
		= true;
}

void removeQueen(int row, int col) {
	usedColumn[col]
		= usedMainDiag[row - col + N - 1]
		= usedSndDiag[row + col]
		= false;
}

void findAllSolutions(int row) {

	if (row == N) {
		numberOfSolutions++;

		if (numberOfSolutions == 1) {
			printFirstSolution();
		}
		return;
	}

	for (int col = 0; col < N; col++) {
		if (isSafe(row, col)) {
			putQueen(row, col);
			solution[row] = col + 1;

			findAllSolutions(row + 1);

			removeQueen(row, col);
		}
	}

	return;
}

int main(void) {

	fin = fopen("damesah.in", "r");
	fscanf(fin, "%d", &N);
	fclose(fin);

	fout = fopen("damesah.out", "w");

	findAllSolutions(0);

	fprintf(fout, "%d", numberOfSolutions);
	fclose(fout);

	return 0;
}