def is_valid(last_added, index):
    if last_added in partial_solution[:index]:
        return False

    for i in range(index):
        line = i + 1
        col = partial_solution[i]

        # primary diagonal
        if line == col and last_added == index + 1:
            return False

        # secondary diagonal
        if line + col == n + 1 and last_added + index == n:
            return False

        diff = abs(line - col)
        # parallel to the primary diagonal
        if abs(index + 1 - last_added) == diff and (
                (line > col and index + 1 > last_added) or (line < col and index + 1 < last_added)):
            return False

        summ = line + col
        # parallel to the secondary diagonal
        if summ == last_added + index + 1 and (
                (line + col > n + 1 and index + last_added > n) or (line + col < n + 1 and index + last_added < n)):
            return False

    return True


def is_solution(index):
    if index < n - 1:
        return False
    return True


def show_solution():
    file = open("damesah.out", "w")
    # for idx in range(n):
    #     line = ""
    #     for j in range(1, n + 1):
    #         if partial_solution[idx] == j:
    #             line += "* "
    #         else:
    #             line += "- "
    #     file.write(line + "\n")
    solution = ""
    for i in first_solution:
        solution += str(i) + " "
    file.write(solution)
    file.write("\n"+str(total_solutions))
    file.close()


def backtracking(index):
    global total_solutions, is_first_sol, first_solution
    for i in range(1, n + 1):
        if is_valid(i, index):
            partial_solution.insert(index, i)
            if is_solution(index):
                if not is_first_sol:
                    first_solution = partial_solution[:index+1]
                    show_solution()
                    is_first_sol = True
                total_solutions = total_solutions + 1
            else:
                backtracking(index + 1)


is_first_sol = False
file = open("damesah.in", "r")
n = int(file.read())
file.close()

partial_solution = []
first_solution = []
total_solutions = 0

backtracking(0)
show_solution()