/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P01NQueens {
	private static final String FileOutputName = "nQueens.out";

	public static void main(String[] args) throws IOException {
		PrintStream out = new PrintStream(new File(FileOutputName));
		try {
			System.out.print(" n = ");
			Scanner sc = new Scanner(System.in);
			if (!sc.hasNextInt()) {
				return;
			}
			int n = sc.nextInt();
			int noSol = 0;
			int[] x = new int[n];
			int k = 0;
			x[k] = -1;
			while (k >= 0) {
				boolean flag = false;
				while (!flag && x[k] < n - 1) {
					x[k]++;
					flag = true;
					for (int i = 0; i < k; i++)
						if (x[i] == x[k] || Math.abs(x[i] - x[k]) == k - i)
							flag = false;
				}
				if (flag) {
					if (k == n - 1) {
						for (int i : x) {
							out.print(i + 1);
							out.print(' ');
						}
						out.println();
						noSol++;
					} else
						x[++k] = -1;
				} else
					k--;
			}
			out.print(n);
			out.print(' ');
			out.println(noSol);
		} finally {
			out.close();
		}
	}
}