queens array

def dfs(cols, diags, rdiags, queens, y, n, res):
    if y == n:
        res.append(queens[:])
        return
    for x in range(n):
        if cols[x] == diags[x-y] == rdiags[x+y] == False:
            cols[x] = diags[x-y] = rdiags[x+y] = True
            queens[y] = x + 1
            dfs(cols, diags, rdiags, queens, y+1, n, res)
            cols[x] = diags[x-y] = rdiags[x+y] = False


def get_combs(n):
    cols = [False] * n
    diags = [False] * 2 * n
    rdiags = [False] * 2 * n
    queens = [0] * n
    res = []
    dfs(cols, diags, rdiags, queens, 0, n, res)
    return res


n = int(input())
res = get_combs(n)
print(len(res))
for queens in res:
    print(' '.join([str(x) for x in queens]))