def backtracking(k):
    global ans, dame, n
    for i in range(1, n + 1):
        dame[k] = i
        if valid(k):
            if solutie(k):
                if ans == 0:
                    afiseaza(k)
                ans += 1
            else:
                backtracking(k + 1)

def valid(k):
    global dame, n
    if k == 1:
        return True
    for i in range(1, k):
        if dame[i] == dame[k] or abs(dame[i] - dame[k]) == abs(i - k):
            return False
    return True

def solutie(k):
    global n
    if k == n:
        return True
    return False

def afiseaza(k):
    global dame, n
    for i in range(1, n + 1):
        print(dame[i], end = ' ', file = f)
    print('', file = f)

with open('damesah.in') as f:
    n = int(f.readline())

#n = int(input())

ans = 0
dame = [0] * (n+1)

with open('damesah.out', 'w') as f:
    backtracking(1)
    print(ans, file = f)