# Place n non-attacking queens on a nxn chessboard with no queen on either of the major diagonals

import sys, random

n = int(sys.argv[1])

# Every square that a queen may be placed
squares = set([(i,j) for i in range(n) for j in range(n) if i != j and i + j != n-1])
# Every square attacked from this square
canattack = lambda (i0,j0), (i1,j1): i0 == i1 or j0 == j1 or abs(i0 - i1) == abs(j0 - j1)
attacks = dict((s, set([s2 for s2 in squares if canattack(s, s2)])) for s in squares)

# nleft = number of queens still to place
# free = squares where a queen can still be placed
def solve(nleft = n, free = squares):
    if nleft > len(free): return None
    if nleft == 1: return tuple(free)
    # Squares that will still remain if the given square is taken
    newfree = dict((square, free - attacks[square]) for square in free)
    # Start with the placements that will leave the most remaining squares
    # If there's a tie, shuffle them randomly (to make this nondeterministic)
    tocheck = sorted(free, key = lambda s: (len(newfree[s]), random.random()), reverse = True)
    for square in tocheck:
        solution = solve(nleft - 1, newfree[square])
        if solution:
            return solution + (square,)
    return None

board = solve()
for i in range(n):
    for j in range(n):
        print ("Q" if (i,j) in board else "."),
    print