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 backtracking(index):
    global total_solutions, first_sol
    for i in range(1, n + 1):
        if is_valid(i, index):
            partial_solution.insert(index, i)
            # print(">", i, partial_solution[:index + 1])
            if is_solution(index):
                if not first_sol:
                    print(partial_solution[:n])
                    first_sol = True
                total_solutions = total_solutions + 1
            else:
                backtracking(index + 1)


first_sol = False
n = int(input("Give n (between 4 and 13): "))
partial_solution = []
total_solutions = 0
backtracking(0)
print(total_solutions)