import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Solver {
    private int N;
    private BlockType[][] board;
    private boolean[] visitedVariables;
    private Integer[] assignments;
    private ArrayList<Integer[]> solutions;

    public Solver(int N) {
        this.N = N;
        board = new BlockType[N][N];
        assignments = new Integer[N];
        visitedVariables = new boolean[N];
        solutions = new ArrayList<Integer[]>();

        csp();
    }

    private void csp() {
        Integer v = getNextUnvisitedVariable();
        if (v == null)  {
            // No unassigned variables, found a solution
            solutions.add(Arrays.copyOf(assignments, assignments.length));

            for (int i = 0; i < N; i++)
                assert(isAssignmentValid(i, assignments[i]));
        }
        else {
            visitedVariables[v] = true;

            for (int i = 0; i < N; i++) {
                if (isAssignmentValid(v, i)) {
                    board[v][i] = BlockType.Q;
                    assignments[v] = i;
                    List<BoardPosition> conflictedPositions = forwardChecking(v, i);
                    csp();
                    undoForwardChecking(conflictedPositions);
                    assignments[v] = null;
                    board[v][i] = BlockType.None;
                }
            }

            visitedVariables[v] = false;
        }
    }

    private Integer getNextUnvisitedVariable() {
        int minimumRemainingValue = Integer.MAX_VALUE;
        Integer minimumRemainingValueNode = null;

        for (int i = 0; i < visitedVariables.length; i++) {
            if (!visitedVariables[i]) {
                int remaninigValue = getRemainingValue(i);
                if (remaninigValue < minimumRemainingValue) {
                    minimumRemainingValue = remaninigValue;
                    minimumRemainingValueNode = i;
                }
            }

        }

        return minimumRemainingValueNode;
    }

    private List<BoardPosition> forwardChecking(int row, int col) {
        List<BoardPosition> conflictedPositions = new ArrayList<BoardPosition>();
        for (int i = 0; i < N; i++) {
            if (i == row)
                continue;
            checkBord(i, col, conflictedPositions);
            checkBord(i, col - (row - i), conflictedPositions);
            checkBord(i, col + (row - i), conflictedPositions);
        }

        return conflictedPositions;
    }

    private void undoForwardChecking(List<BoardPosition> conflictedPositions) {
        for (BoardPosition boardPosition : conflictedPositions) {
            board[boardPosition.row][boardPosition.col] = BlockType.None;
        }
    }

    private void checkBord(int row, int col, List<BoardPosition> conflictedPositions) {
        if (isValidPosition(row, col) && board[row][col] == BlockType.None) {
            board[row][col] = BlockType.X;
            conflictedPositions.add(new BoardPosition(row, col));
        }
    }

    private int getRemainingValue(int row) {
        int remainingValues = 0;
        for (int i = 0; i < N; i++) {
            if (board[row][i] == BlockType.X)
                remainingValues++;
        }

        return remainingValues;
    }

    private boolean isAssignmentValid(int row, int col) {
        for (int i = 0; i < N; i++) {
            if (i == row)
                continue;
            if (board[i][col] == BlockType.Q)
                return false;

            if (isValidPosition(row, col - (row - i)) && board[i][col - (row - i)] == BlockType.Q)
                return false;

            if (isValidPosition(row, col + (row - i)) && board[i][col + (row - i)] == BlockType.Q)
                return false;
        }

        return true;
    }

    private boolean isValidPosition(int row, int col) {
        return row >= 0 && row < N && col >= 0 && col < N;
    }

    public ArrayList<Integer[]> getSolutions() {
        return solutions;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        Solver solver = new Solver(N);

        for (Integer assignment : solver.getSolutions().get(0))
            System.out.print((assignment + 1) + " ");
        System.out.println();
        System.out.println(solver.getSolutions().size());

        for (Integer[] solution : solver.getSolutions()) {
            for (Integer assignment : solution)
                System.out.print((assignment + 1) + " ");
            System.out.println();
        }
    }

    public enum BlockType {Q, None, X}

    public class BoardPosition {
        public int row;
        public int col;

        public BoardPosition(int row, int col) {
            this.row = row;
            this.col = col;
        }

    }
}