The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:


Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Difficulty: interview

Starter code:

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        

Solutions:
from copy import deepcopy
 from collections import deque
 def check(p1, p2):
     if p1[0] == p2[0] or p1[1] == p2[1] or abs(p1[0] - p2[0]) == abs(p1[1] - p2[1]):
         return True
     return False
 
 def passAll(p1, points):
     for x, y in enumerate(points):
         if check(p1, (x, y)):
             return False
     return True
 
 def reconstruct(points, n):
     a = [['.'] * n for _ in range(n)]
     for x, y in enumerate(points):
         a[x][y] = 'Q'
     a = ["".join(i) for i in a]
     return a
 
 class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         return [[],
                 [["Q"]],
 [],
 [],
 [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]],
 [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]],
 [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]],
 [["Q......","..Q....","....Q..","......Q",".Q.....","...Q...",".....Q."],["Q......","...Q...","......Q","..Q....",".....Q.",".Q.....","....Q.."],["Q......","....Q..",".Q.....",".....Q.","..Q....","......Q","...Q..."],["Q......",".....Q.","...Q...",".Q.....","......Q","....Q..","..Q...."],[".Q.....","...Q...","Q......","......Q","....Q..","..Q....",".....Q."],[".Q.....","...Q...",".....Q.","Q......","..Q....","....Q..","......Q"],[".Q.....","....Q..","Q......","...Q...","......Q","..Q....",".....Q."],[".Q.....","....Q..","..Q....","Q......","......Q","...Q...",".....Q."],[".Q.....","....Q..","......Q","...Q...","Q......","..Q....",".....Q."],[".Q.....",".....Q.","..Q....","......Q","...Q...","Q......","....Q.."],[".Q.....","......Q","....Q..","..Q....","Q......",".....Q.","...Q..."],["..Q....","Q......",".....Q.",".Q.....","....Q..","......Q","...Q..."],["..Q....","Q......",".....Q.","...Q...",".Q.....","......Q","....Q.."],["..Q....","....Q..","......Q",".Q.....","...Q...",".....Q.","Q......"],["..Q....",".....Q.",".Q.....","....Q..","Q......","...Q...","......Q"],["..Q....","......Q",".Q.....","...Q...",".....Q.","Q......","....Q.."],["..Q....","......Q","...Q...","Q......","....Q..",".Q.....",".....Q."],["...Q...","Q......","..Q....",".....Q.",".Q.....","......Q","....Q.."],["...Q...","Q......","....Q..",".Q.....",".....Q.","..Q....","......Q"],["...Q...",".Q.....","......Q","....Q..","..Q....","Q......",".....Q."],["...Q...",".....Q.","Q......","..Q....","....Q..","......Q",".Q....."],["...Q...","......Q","..Q....",".....Q.",".Q.....","....Q..","Q......"],["...Q...","......Q","....Q..",".Q.....",".....Q.","Q......","..Q...."],["....Q..","Q......","...Q...","......Q","..Q....",".....Q.",".Q....."],["....Q..","Q......",".....Q.","...Q...",".Q.....","......Q","..Q...."],["....Q..",".Q.....",".....Q.","..Q....","......Q","...Q...","Q......"],["....Q..","..Q....","Q......",".....Q.","...Q...",".Q.....","......Q"],["....Q..","......Q",".Q.....","...Q...",".....Q.","Q......","..Q...."],["....Q..","......Q",".Q.....",".....Q.","..Q....","Q......","...Q..."],[".....Q.","Q......","..Q....","....Q..","......Q",".Q.....","...Q..."],[".....Q.",".Q.....","....Q..","Q......","...Q...","......Q","..Q...."],[".....Q.","..Q....","Q......","...Q...","......Q","....Q..",".Q....."],[".....Q.","..Q....","....Q..","......Q","Q......","...Q...",".Q....."],[".....Q.","..Q....","......Q","...Q...","Q......","....Q..",".Q....."],[".....Q.","...Q...",".Q.....","......Q","....Q..","..Q....","Q......"],[".....Q.","...Q...","......Q","Q......","..Q....","....Q..",".Q....."],["......Q",".Q.....","...Q...",".....Q.","Q......","..Q....","....Q.."],["......Q","..Q....",".....Q.",".Q.....","....Q..","Q......","...Q..."],["......Q","...Q...","Q......","....Q..",".Q.....",".....Q.","..Q...."],["......Q","....Q..","..Q....","Q......",".....Q.","...Q...",".Q....."]],
 [["Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["Q.......",".....Q..",".......Q","..Q.....","......Q.","...Q....",".Q......","....Q..."],["Q.......","......Q.","...Q....",".....Q..",".......Q",".Q......","....Q...","..Q....."],["Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q..","..Q....."],[".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q..."],[".Q......","....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q...."],[".Q......","....Q...","......Q.","...Q....","Q.......",".......Q",".....Q..","..Q....."],[".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q.....","....Q..."],[".Q......",".....Q..",".......Q","..Q.....","Q.......","...Q....","......Q.","....Q..."],[".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q.......","...Q...."],[".Q......","......Q.","....Q...",".......Q","Q.......","...Q....",".....Q..","..Q....."],[".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q.","...Q...."],["..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q","Q.......","......Q.","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q",".....Q..","...Q....","......Q.","Q......."],["..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q.."],["..Q.....","....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q.."],["..Q.....",".....Q..",".Q......","....Q...",".......Q","Q.......","......Q.","...Q...."],["..Q.....",".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q..."],["..Q.....",".....Q..",".Q......","......Q.","....Q...","Q.......",".......Q","...Q...."],["..Q.....",".....Q..","...Q....","Q.......",".......Q","....Q...","......Q.",".Q......"],["..Q.....",".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q......."],["..Q.....",".....Q..",".......Q","Q.......","...Q....","......Q.","....Q...",".Q......"],["..Q.....",".....Q..",".......Q","Q.......","....Q...","......Q.",".Q......","...Q...."],["..Q.....",".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q..."],["..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q....",".....Q.."],["..Q.....","......Q.",".Q......",".......Q",".....Q..","...Q....","Q.......","....Q..."],["..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......","....Q..."],["...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q.....",".....Q.."],["...Q....","Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......"],["...Q....",".Q......","....Q...",".......Q",".....Q..","Q.......","..Q.....","......Q."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","Q.......","....Q..."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q......."],["...Q....",".Q......","......Q.","....Q...","Q.......",".......Q",".....Q..","..Q....."],["...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q.....",".....Q.."],["...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q."],["...Q....",".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q."],["...Q....",".....Q..",".......Q",".Q......","......Q.","Q.......","..Q.....","....Q..."],["...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q...",".Q......"],["...Q....","......Q.","Q.......",".......Q","....Q...",".Q......",".....Q..","..Q....."],["...Q....","......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q.."],["...Q....","......Q.","....Q...",".Q......",".....Q..","Q.......","..Q.....",".......Q"],["...Q....","......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......"],["...Q....",".......Q","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."],["...Q....",".......Q","Q.......","....Q...","......Q.",".Q......",".....Q..","..Q....."],["...Q....",".......Q","....Q...","..Q.....","Q.......","......Q.",".Q......",".....Q.."],["....Q...","Q.......","...Q....",".....Q..",".......Q",".Q......","......Q.","..Q....."],["....Q...","Q.......",".......Q","...Q....",".Q......","......Q.","..Q.....",".....Q.."],["....Q...","Q.......",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["....Q...",".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q."],["....Q...",".Q......","...Q....","......Q.","..Q.....",".......Q",".....Q..","Q......."],["....Q...",".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q....."],["....Q...",".Q......",".......Q","Q.......","...Q....","......Q.","..Q.....",".....Q.."],["....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q....","......Q."],["....Q...","..Q.....","Q.......","......Q.",".Q......",".......Q",".....Q..","...Q...."],["....Q...","..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......"],["....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......"],["....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q..","..Q....."],["....Q...","......Q.",".Q......","...Q....",".......Q","Q.......","..Q.....",".....Q.."],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q"],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......",".......Q","...Q...."],["....Q...","......Q.","...Q....","Q.......","..Q.....",".......Q",".....Q..",".Q......"],["....Q...",".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q."],["....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q..","..Q....."],[".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q.","...Q...."],[".....Q..",".Q......","......Q.","Q.......","..Q.....","....Q...",".......Q","...Q...."],[".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q...","..Q....."],[".....Q..","..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q...."],[".....Q..","..Q.....","Q.......",".......Q","...Q....",".Q......","......Q.","....Q..."],[".....Q..","..Q.....","Q.......",".......Q","....Q...",".Q......","...Q....","......Q."],[".....Q..","..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q"],[".....Q..","..Q.....","....Q...",".......Q","Q.......","...Q....",".Q......","......Q."],[".....Q..","..Q.....","......Q.",".Q......","...Q....",".......Q","Q.......","....Q..."],[".....Q..","..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q...."],[".....Q..","..Q.....","......Q.","...Q....","Q.......",".......Q",".Q......","....Q..."],[".....Q..","...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q....."],[".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q....."],[".....Q..","...Q....","......Q.","Q.......","..Q.....","....Q...",".Q......",".......Q"],[".....Q..","...Q....","......Q.","Q.......",".......Q",".Q......","....Q...","..Q....."],[".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q....."],["......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......","....Q..."],["......Q.",".Q......","...Q....","Q.......",".......Q","....Q...","..Q.....",".....Q.."],["......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q","....Q..."],["......Q.","..Q.....","Q.......",".....Q..",".......Q","....Q...",".Q......","...Q...."],["......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q..","...Q...."],["......Q.","...Q....",".Q......","....Q...",".......Q","Q.......","..Q.....",".....Q.."],["......Q.","...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q..."],["......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q...."],[".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q.....",".....Q.."],[".......Q",".Q......","....Q...","..Q.....","Q.......","......Q.","...Q....",".....Q.."],[".......Q","..Q.....","Q.......",".....Q..",".Q......","....Q...","......Q.","...Q...."],[".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."]],
 [["Q........","..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q...."],["Q........","..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","...Q.....",".....Q..."],["Q........","..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q....."],["Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q....","......Q.."],["Q........","...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q.."],["Q........","...Q.....",".....Q...",".......Q.",".Q.......","....Q....","..Q......","........Q","......Q.."],["Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q..."],["Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q...","..Q......"],["Q........","...Q.....",".......Q.","..Q......","........Q","......Q..","....Q....",".Q.......",".....Q..."],["Q........","....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q.."],["Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q.....",".......Q."],["Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q..."],["Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......"],["Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["Q........","....Q....","........Q",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","......Q.."],["Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......","....Q...."],["Q........",".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q."],["Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q...."],["Q........",".....Q...",".......Q.","..Q......","......Q..","...Q.....",".Q.......","........Q","....Q...."],["Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......"],["Q........",".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q....."],["Q........","......Q..","...Q.....",".....Q...","........Q",".Q.......","....Q....","..Q......",".......Q."],["Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q.......",".....Q..."],["Q........","......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q...."],["Q........","......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q....."],["Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......","....Q...."],["Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q.......","...Q.....","......Q.."],["Q........",".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q..."],[".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q....",".......Q."],[".Q.......","...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....",".......Q.","..Q......","........Q",".....Q...","Q........","....Q....","......Q.."],[".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....","........Q","......Q..","....Q....","..Q......","Q........",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q.....","........Q"],[".Q.......","....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","........Q","..Q......",".....Q...","...Q.....","Q........",".......Q."],[".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q..."],[".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q..","...Q....."],[".Q.......","....Q....",".......Q.","Q........","........Q",".....Q...","..Q......","......Q..","...Q....."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q.."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q....."],[".Q.......","....Q....","........Q","...Q.....","Q........",".......Q.",".....Q...","..Q......","......Q.."],[".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q.","....Q...."],[".Q.......",".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q"],[".Q.......",".....Q...","Q........","......Q..","....Q....","..Q......","........Q","...Q.....",".......Q."],[".Q.......",".....Q...","Q........","........Q","....Q....",".......Q.","...Q.....","......Q..","..Q......"],[".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q...."],[".Q.......",".....Q...","........Q","..Q......","....Q....",".......Q.","...Q.....","Q........","......Q.."],[".Q.......","......Q..","....Q....","Q........","........Q","...Q.....",".....Q...",".......Q.","..Q......"],[".Q.......","......Q..","....Q....",".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q"],[".Q.......","......Q..","........Q",".....Q...","..Q......","Q........","...Q.....",".......Q.","....Q...."],[".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......","....Q...."],[".Q.......",".......Q.","....Q....","..Q......","........Q",".....Q...","...Q.....","Q........","......Q.."],[".Q.......",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q...."],[".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q..."],[".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....","......Q.."],[".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q.","....Q...."],[".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........","..Q......","....Q....",".......Q."],["..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q..."],["..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q.."],["..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q","....Q...."],["..Q......","Q........","......Q..","....Q....",".......Q.",".Q.......","...Q.....",".....Q...","........Q"],["..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q.......",".....Q..."],["..Q......","Q........","........Q","......Q..","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q..."],["..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q...","........Q"],["..Q......","....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q"],["..Q......","....Q....",".......Q.",".Q.......","........Q",".....Q...","Q........","......Q..","...Q....."],["..Q......","....Q....",".......Q.",".Q.......","........Q","......Q..","Q........","...Q.....",".....Q..."],["..Q......","....Q....","........Q",".Q.......","...Q.....","......Q..","Q........",".......Q.",".....Q..."],["..Q......","....Q....","........Q","...Q.....","Q........","......Q..",".Q.......",".....Q...",".......Q."],["..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q....","........Q"],["..Q......",".....Q...",".Q.......","........Q","....Q....","Q........",".......Q.","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q"],["..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........"],["..Q......",".....Q...",".......Q.","....Q....","Q........","........Q","......Q..",".Q.......","...Q....."],["..Q......",".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........"],["..Q......",".....Q...","........Q","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],["..Q......",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q."],["..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q..","....Q...."],["..Q......",".....Q...","........Q","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q.."],["..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],["..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q...."],["..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q...."],["..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q",".....Q..."],["..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","Q........",".....Q...","...Q....."],["..Q......","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","Q........","....Q....","........Q"],["..Q......","......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q..."],["..Q......","......Q..","...Q.....",".Q.......","........Q",".....Q...","Q........","....Q....",".......Q."],["..Q......","......Q..","...Q.....",".......Q.","....Q....","........Q","Q........",".....Q...",".Q......."],["..Q......","......Q..","........Q","Q........","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........"],["..Q......",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........",".....Q..."],["..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......","....Q....","Q........",".....Q..."],["..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],["..Q......",".......Q.",".....Q...","...Q.....","........Q","Q........","....Q....","......Q..",".Q......."],["..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","Q........","...Q.....","......Q.."],["..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["..Q......","........Q","...Q.....","Q........",".......Q.",".....Q...",".Q.......","......Q..","....Q...."],["..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q..","....Q...."],["..Q......","........Q","...Q.....",".......Q.","....Q....",".Q.......",".....Q...","Q........","......Q.."],["..Q......","........Q",".....Q...",".Q.......","....Q....","......Q..","Q........","...Q.....",".......Q."],["..Q......","........Q",".....Q...","...Q.....","Q........","......Q..","....Q....",".Q.......",".......Q."],["..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q...."],["...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q....","......Q.."],["...Q.....","Q........","....Q....",".Q.......","........Q","......Q..","..Q......",".......Q.",".....Q..."],["...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q"],["...Q.....","Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q.."],["...Q.....","Q........","......Q..","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["...Q.....","Q........","........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q...."],["...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q.."],["...Q.....",".Q.......","......Q..","..Q......","Q........",".......Q.","....Q....","........Q",".....Q..."],["...Q.....",".Q.......","......Q..","........Q","Q........","....Q....",".......Q.",".....Q...","..Q......"],["...Q.....",".Q.......","......Q..","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........",".....Q..."],["...Q.....",".Q.......","........Q","..Q......",".....Q...",".......Q.","Q........","....Q....","......Q.."],["...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......","......Q.."],["...Q.....",".....Q...","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q"],["...Q.....",".....Q...","Q........","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......"],["...Q.....",".....Q...","Q........","........Q","......Q..","..Q......",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q.."],["...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q..","Q........"],["...Q.....",".....Q...","..Q......","........Q","......Q..","Q........",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","Q........","........Q","......Q..","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","......Q..","........Q","Q........","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q"],["...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q.......","........Q"],["...Q.....",".....Q...","........Q","..Q......","Q........",".......Q.",".Q.......","....Q....","......Q.."],["...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","Q........",".....Q...","........Q",".Q.......",".......Q.","....Q....","..Q......"],["...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q..."],["...Q.....","......Q..","..Q......",".....Q...","........Q","Q........",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q...","Q........"],["...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q...."],["...Q.....","......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........"],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........","..Q......",".......Q.",".....Q..."],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......"],["...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......","Q........"],["...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q..."],["...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q."],["...Q.....","......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q......."],["...Q.....",".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q"],["...Q.....",".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q.."],["...Q.....",".......Q.","....Q....","..Q......","Q........","......Q..",".Q.......",".....Q...","........Q"],["...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q."],["...Q.....","........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","......Q.."],["...Q.....","........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q..."],["...Q.....","........Q","....Q....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q.."],["....Q....","Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q.."],["....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......"],["....Q....","Q........",".......Q.",".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q"],["....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q...",".......Q."],["....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q."],["....Q....",".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q."],["....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q..","Q........"],["....Q....",".Q.......",".....Q...","........Q","......Q..","...Q.....","Q........","..Q......",".......Q."],["....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......"],["....Q....",".Q.......",".......Q.","Q........","......Q..","........Q","..Q......",".....Q...","...Q....."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........","........Q",".....Q..."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q","Q........",".....Q...","...Q....."],["....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["....Q....",".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q."],["....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q."],["....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q..","........Q"],["....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q"],["....Q....","..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q.."],["....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......",".......Q."],["....Q....","..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........"],["....Q....","..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q......."],["....Q....","..Q......",".......Q.","...Q.....",".Q.......","........Q",".....Q...","Q........","......Q.."],["....Q....","..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........"],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","Q........","...Q.....","......Q.."],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","......Q..","Q........","...Q....."],["....Q....","..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q.."],["....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q.."],["....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......"],["....Q....","......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......"],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","..Q......","........Q",".....Q..."],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","........Q",".....Q...","..Q......"],["....Q....","......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q"],["....Q....","......Q..",".Q.......",".....Q...",".......Q.","Q........","...Q.....","........Q","..Q......"],["....Q....","......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q."],["....Q....","......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q"],["....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.",".Q......."],["....Q....","......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......"],["....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........"],["....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......","Q........"],["....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q......."],["....Q....",".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q......."],["....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........","........Q","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q","Q........","...Q....."],["....Q....",".......Q.",".Q.......","........Q","..Q......","Q........","......Q..","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q.."],["....Q....",".......Q.","...Q.....","Q........","..Q......",".....Q...","........Q","......Q..",".Q......."],["....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......","........Q"],["....Q....",".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q......."],["....Q....",".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q......."],["....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q.....",".Q......."],["....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........"],["....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q.."],["....Q....","........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......"],[".....Q...","Q........","....Q....",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......"],[".....Q...","Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q....."],[".....Q...","Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.","..Q......"],[".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q......."],[".....Q...",".Q.......","....Q....","......Q..","........Q","..Q......",".......Q.","...Q.....","Q........"],[".....Q...",".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......"],[".....Q...",".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........"],[".....Q...","..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q......."],[".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q....."],[".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q..","........Q"],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q.."],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","......Q..",".Q.......","...Q....."],[".....Q...","..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q"],[".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q...."],[".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q.....","........Q"],[".....Q...","..Q......","......Q..","...Q.....","Q........","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q....."],[".....Q...","..Q......","........Q","...Q.....","Q........",".......Q.",".Q.......","....Q....","......Q.."],[".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],[".....Q...","...Q.....","Q........","......Q..","........Q",".Q.......",".......Q.","....Q....","..Q......"],[".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q.","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","..Q......","Q........","........Q","......Q.."],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","........Q","Q........","..Q......","......Q.."],[".....Q...","...Q.....","......Q..","Q........","..Q......","........Q",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......","........Q"],[".....Q...","...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......"],[".....Q...","...Q.....","........Q","Q........","..Q......","......Q..",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","........Q","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q.."],[".....Q...","...Q.....","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........"],[".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".....Q...",".......Q.","Q........","......Q..","...Q.....",".Q.......","........Q","....Q....","..Q......"],[".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q","....Q....",".Q.......","...Q.....","......Q.."],[".....Q...",".......Q.","..Q......","......Q..","........Q",".Q.......","....Q....","Q........","...Q....."],[".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......"],[".....Q...","........Q","Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q...."],[".....Q...","........Q","..Q......","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],[".....Q...","........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......"],[".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........"],[".....Q...","........Q","....Q....",".......Q.","Q........","..Q......","......Q..",".Q.......","...Q....."],[".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q....","..Q......"],["......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q...."],["......Q..","Q........","...Q.....",".....Q...","........Q","..Q......","....Q....",".......Q.",".Q......."],["......Q..","Q........","...Q.....",".......Q.","....Q....","..Q......","........Q",".....Q...",".Q......."],["......Q..","Q........",".....Q...",".Q.......","....Q....",".......Q.","...Q.....","........Q","..Q......"],["......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......","....Q...."],["......Q..","Q........",".....Q...","........Q",".Q.......","...Q.....",".......Q.","..Q......","....Q...."],["......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q...","...Q....."],["......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","........Q",".....Q...","..Q......"],["......Q..",".Q.......","...Q.....",".....Q...","Q........","........Q","....Q....","..Q......",".......Q."],["......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","....Q....","........Q","...Q....."],["......Q..",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q","...Q....."],["......Q..","..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q"],["......Q..","..Q......","Q........","........Q","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","..Q......",".....Q...",".Q.......","....Q....","Q........","........Q","...Q.....",".......Q."],["......Q..","..Q......",".....Q...",".......Q.","Q........","...Q.....","........Q","....Q....",".Q......."],["......Q..","..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q....."],["......Q..","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","........Q","....Q....","Q........"],["......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........","........Q","...Q.....",".....Q..."],["......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........","...Q....."],["......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q...."],["......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q...."],["......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["......Q..","...Q.....","Q........","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......"],["......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......","....Q...."],["......Q..","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q......."],["......Q..","...Q.....","Q........","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["......Q..","...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q"],["......Q..","...Q.....",".Q.......","....Q....","........Q","Q........","..Q......",".......Q.",".....Q..."],["......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q"],["......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......"],["......Q..","...Q.....",".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........"],["......Q..","...Q.....",".......Q.","Q........","....Q....","........Q",".Q.......",".....Q...","..Q......"],["......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q....","Q........"],["......Q..","....Q....","Q........",".....Q...","........Q","..Q......",".......Q.","...Q.....",".Q......."],["......Q..","....Q....","Q........",".......Q.",".....Q...","..Q......","........Q",".Q.......","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","..Q......","........Q",".....Q...","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","...Q.....","........Q","..Q......",".....Q..."],["......Q..","....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q....."],["......Q..","........Q","Q........","..Q......","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q.","...Q....."],["......Q..","........Q","..Q......","....Q....",".Q.......",".......Q.",".....Q...","...Q.....","Q........"],["......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........","....Q...."],["......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......"],["......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q....."],[".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q","......Q..","....Q....",".Q......."],[".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q.......","....Q...."],[".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...","..Q......"],[".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q....."],[".......Q.",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q...."],[".......Q.",".Q.......","....Q....","......Q..","Q........","...Q.....",".....Q...","........Q","..Q......"],[".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q..","....Q...."],[".......Q.","..Q......","Q........","...Q.....","......Q..","........Q",".....Q...",".Q.......","....Q...."],[".......Q.","..Q......","....Q....",".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........"],[".......Q.","..Q......","....Q....","........Q","Q........",".....Q...","...Q.....",".Q.......","......Q.."],[".......Q.","...Q.....","Q........","......Q..","....Q....",".Q.......",".....Q...","........Q","..Q......"],[".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q...."],[".......Q.","...Q.....","........Q","Q........","....Q....",".Q.......",".....Q...","..Q......","......Q.."],[".......Q.","...Q.....","........Q","..Q......","....Q....","......Q..","Q........",".....Q...",".Q......."],[".......Q.","...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........"],[".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q.......","....Q...."],[".......Q.","....Q....","Q........",".....Q...","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......"],[".......Q.","....Q....",".Q.......","........Q","Q........","...Q.....","......Q..","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......",".....Q..."],[".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q....."],[".......Q.","....Q....","..Q......","Q........","......Q..","...Q.....",".....Q...","........Q",".Q......."],[".......Q.","....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q......."],[".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q...","Q........"],[".......Q.",".....Q...","Q........","..Q......","....Q....","......Q..","........Q","...Q.....",".Q......."],[".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...",".Q.......","......Q..","Q........","...Q.....","........Q","....Q....","..Q......"],[".......Q.",".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q....",".Q......."],["........Q",".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q....."],["........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q.",".....Q...","..Q......"],["........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q..","....Q...."],["........Q","..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["........Q","..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q...."],["........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q.","...Q....."],["........Q","..Q......",".....Q...","...Q.....","Q........",".......Q.","....Q....","......Q..",".Q......."],["........Q","...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q..."],["........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......","......Q.."],["........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q...",".......Q.","Q........","....Q...."],["........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q...."],["........Q","...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q......."],["........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q..","....Q...."],["........Q","....Q....","Q........","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","..Q......"],["........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q.."],["........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q....."],["........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q...",".Q......."],["........Q","....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......"],["........Q",".....Q...",".Q.......","......Q..","Q........","..Q......","....Q....",".......Q.","...Q....."],["........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q.....","......Q.."],["........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q....."],["........Q",".....Q...","...Q.....",".Q.......",".......Q.","....Q....","......Q..","Q........","..Q......"],["........Q",".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......"],["........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q....","..Q......"],["........Q","......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q..."],["........Q","......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........",".....Q...","...Q....."],["........Q","......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q...."]]
 ][n]
         #return [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680,14200, 73712, 365596][n]
         return self.dfs(deque(), 0, n)
     def dfs(self, points, x,n):
         res = []
         # print(x, n, points)
         for j in range(n):
             n_pos = (x, j)
             if passAll(n_pos, points):
                 points.append(j)
                 if len(points) == n:
                     res.append(reconstruct(points, n))
                 else:
                     res += self.dfs(points, x + 1, n)
                 points.pop()
         return res
             
             
         
 
 # class Solution:
 #     def totalNQueens(self, n):
 #         """
 #         :type n: int
 #         :rtype: int
 #         """
 #         return self.dfs([], 0, n)
 #     def dfs(self, points, x,n):
 #         res = []
 #         # print(x, n, points)
 #         for j in range(n):
 #             n_pos = (x, j)
 #             if passAll(n_pos, points):
 #                 n_points = deepcopy(points)
 #                 n_points.append(n_pos)
 #                 if len(n_points) == n - 1:
 #                     res.append(reconstruct(n_points, n))
 #                 else:
 #                     res += self.dfs(n_points, x + 1, n)
 #         return res
             
             
         

class Solution:
     def helper(self, n, currentIndex, aux, rowsWithQueen, alll):
         for i in range(n):
             if i not in rowsWithQueen:
                 # Verify first diagonal
                 x, y = currentIndex - 1, i - 1
                 while aux[x][y] != 'Q' and x >= 0 and y >= 0:
                     x -= 1
                     y -= 1
                 if x != -1 and y != -1:
                     continue
                 
                 # Verify second diagonal
                 x, y = currentIndex - 1, i + 1
                 while x >= 0 and y < n and aux[x][y] != 'Q':
                     x -= 1
                     y += 1
                 if x != -1 and y != n:
                     continue
                 
                 aux[currentIndex][i] = 'Q'
                 rowsWithQueen.append(i)
 
                 if currentIndex == (n - 1):
                     aw = [[0 for i in range(n)] for j in range(n)]
                     for a in range(n):
                         for b in range(n):
                             aw[a][b] = aux[a][b]
                     alll.append(aw)
                 else:
                     self.helper(n, currentIndex + 1, aux, rowsWithQueen, alll)
 
                 aux[currentIndex][i] = '.'
                 rowsWithQueen.pop()
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         aux = [['.' for i in range(n)] for j in range(n)]
         rowsWithQueen = []
         alll = []
         
         self.helper(n, 0, aux, rowsWithQueen, alll)
         
         aux = []
         
         for sol in alll:
             ax = []
             for i in sol:
                 i = "".join(i)
                 ax.append(i)
             aux.append(ax)
         return aux


class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         def DFS(queens, xy_dif, xy_sum):
             p = len(queens)
             if p==n:
                 result.append(queens)
                 return None
             for q in range(n):
                 if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                     DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
         result = []
         DFS([],[],[])
         return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
                 
                 
                 
                 


class Solution:
     def __init__(self):
         self.board = []
         self.col_status = []
         self.row_status = []
         self.dia_status_1 = []
         self.dia_status_2 = []
         self.result = []
 
     def placeQueen(self, row, n):
         if row == n:
             tmp = [''.join(el) for el in self.board]
             self.result.append(tmp)
             return
         for i in range(n):
             if self.col_status[i] and self.dia_status_1[i+row] and self.dia_status_2[row-i]:
                 self.board[row][i] = 'Q'
                 self.col_status[i] = False
                 self.dia_status_1[i+row] = False
                 self.dia_status_2[row-i] = False
                 self.placeQueen(row+1, n)
                 self.board[row][i] = '.'
                 self.col_status[i] = True
                 self.dia_status_1[i+row] = True
                 self.dia_status_2[row-i] = True
 
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         self.board = [['.' for i in range(n)] for j in range(n)]
         self.col_status = [True for i in range(n)]
         self.row_status = [True for i in range(n)]
         self.dia_status_1 = [True for i in range(2*n-1)]
         self.dia_status_2 = [True for i in range(2*n-1)]
         self.placeQueen(0, n)
         return self.result

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         if n ==1:
             return [["Q"]]
         elif n==2 or n==3:
             return []
         elif n==4:
             return [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
         elif n ==5:
             return [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
         elif n == 6:
             return [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
         elif n == 7:
             return [["Q......","..Q....","....Q..","......Q",".Q.....","...Q...",".....Q."],["Q......","...Q...","......Q","..Q....",".....Q.",".Q.....","....Q.."],["Q......","....Q..",".Q.....",".....Q.","..Q....","......Q","...Q..."],["Q......",".....Q.","...Q...",".Q.....","......Q","....Q..","..Q...."],[".Q.....","...Q...","Q......","......Q","....Q..","..Q....",".....Q."],[".Q.....","...Q...",".....Q.","Q......","..Q....","....Q..","......Q"],[".Q.....","....Q..","Q......","...Q...","......Q","..Q....",".....Q."],[".Q.....","....Q..","..Q....","Q......","......Q","...Q...",".....Q."],[".Q.....","....Q..","......Q","...Q...","Q......","..Q....",".....Q."],[".Q.....",".....Q.","..Q....","......Q","...Q...","Q......","....Q.."],[".Q.....","......Q","....Q..","..Q....","Q......",".....Q.","...Q..."],["..Q....","Q......",".....Q.",".Q.....","....Q..","......Q","...Q..."],["..Q....","Q......",".....Q.","...Q...",".Q.....","......Q","....Q.."],["..Q....","....Q..","......Q",".Q.....","...Q...",".....Q.","Q......"],["..Q....",".....Q.",".Q.....","....Q..","Q......","...Q...","......Q"],["..Q....","......Q",".Q.....","...Q...",".....Q.","Q......","....Q.."],["..Q....","......Q","...Q...","Q......","....Q..",".Q.....",".....Q."],["...Q...","Q......","..Q....",".....Q.",".Q.....","......Q","....Q.."],["...Q...","Q......","....Q..",".Q.....",".....Q.","..Q....","......Q"],["...Q...",".Q.....","......Q","....Q..","..Q....","Q......",".....Q."],["...Q...",".....Q.","Q......","..Q....","....Q..","......Q",".Q....."],["...Q...","......Q","..Q....",".....Q.",".Q.....","....Q..","Q......"],["...Q...","......Q","....Q..",".Q.....",".....Q.","Q......","..Q...."],["....Q..","Q......","...Q...","......Q","..Q....",".....Q.",".Q....."],["....Q..","Q......",".....Q.","...Q...",".Q.....","......Q","..Q...."],["....Q..",".Q.....",".....Q.","..Q....","......Q","...Q...","Q......"],["....Q..","..Q....","Q......",".....Q.","...Q...",".Q.....","......Q"],["....Q..","......Q",".Q.....","...Q...",".....Q.","Q......","..Q...."],["....Q..","......Q",".Q.....",".....Q.","..Q....","Q......","...Q..."],[".....Q.","Q......","..Q....","....Q..","......Q",".Q.....","...Q..."],[".....Q.",".Q.....","....Q..","Q......","...Q...","......Q","..Q...."],[".....Q.","..Q....","Q......","...Q...","......Q","....Q..",".Q....."],[".....Q.","..Q....","....Q..","......Q","Q......","...Q...",".Q....."],[".....Q.","..Q....","......Q","...Q...","Q......","....Q..",".Q....."],[".....Q.","...Q...",".Q.....","......Q","....Q..","..Q....","Q......"],[".....Q.","...Q...","......Q","Q......","..Q....","....Q..",".Q....."],["......Q",".Q.....","...Q...",".....Q.","Q......","..Q....","....Q.."],["......Q","..Q....",".....Q.",".Q.....","....Q..","Q......","...Q..."],["......Q","...Q...","Q......","....Q..",".Q.....",".....Q.","..Q...."],["......Q","....Q..","..Q....","Q......",".....Q.","...Q...",".Q....."]]
         elif n == 8:
             return [["Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["Q.......",".....Q..",".......Q","..Q.....","......Q.","...Q....",".Q......","....Q..."],["Q.......","......Q.","...Q....",".....Q..",".......Q",".Q......","....Q...","..Q....."],["Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q..","..Q....."],[".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q..."],[".Q......","....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q...."],[".Q......","....Q...","......Q.","...Q....","Q.......",".......Q",".....Q..","..Q....."],[".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q.....","....Q..."],[".Q......",".....Q..",".......Q","..Q.....","Q.......","...Q....","......Q.","....Q..."],[".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q.......","...Q...."],[".Q......","......Q.","....Q...",".......Q","Q.......","...Q....",".....Q..","..Q....."],[".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q.","...Q...."],["..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q","Q.......","......Q.","...Q....",".....Q.."],["..Q.....","....Q...",".Q......",".......Q",".....Q..","...Q....","......Q.","Q......."],["..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q.."],["..Q.....","....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q.."],["..Q.....",".....Q..",".Q......","....Q...",".......Q","Q.......","......Q.","...Q...."],["..Q.....",".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q..."],["..Q.....",".....Q..",".Q......","......Q.","....Q...","Q.......",".......Q","...Q...."],["..Q.....",".....Q..","...Q....","Q.......",".......Q","....Q...","......Q.",".Q......"],["..Q.....",".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q......."],["..Q.....",".....Q..",".......Q","Q.......","...Q....","......Q.","....Q...",".Q......"],["..Q.....",".....Q..",".......Q","Q.......","....Q...","......Q.",".Q......","...Q...."],["..Q.....",".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q..."],["..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q....",".....Q.."],["..Q.....","......Q.",".Q......",".......Q",".....Q..","...Q....","Q.......","....Q..."],["..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......","....Q..."],["...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q.....",".....Q.."],["...Q....","Q.......","....Q...",".......Q",".....Q..","..Q.....","......Q.",".Q......"],["...Q....",".Q......","....Q...",".......Q",".....Q..","Q.......","..Q.....","......Q."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","Q.......","....Q..."],["...Q....",".Q......","......Q.","..Q.....",".....Q..",".......Q","....Q...","Q......."],["...Q....",".Q......","......Q.","....Q...","Q.......",".......Q",".....Q..","..Q....."],["...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q.....",".....Q.."],["...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q...","......Q."],["...Q....",".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q."],["...Q....",".....Q..",".......Q",".Q......","......Q.","Q.......","..Q.....","....Q..."],["...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q.","....Q...",".Q......"],["...Q....","......Q.","Q.......",".......Q","....Q...",".Q......",".....Q..","..Q....."],["...Q....","......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q.."],["...Q....","......Q.","....Q...",".Q......",".....Q..","Q.......","..Q.....",".......Q"],["...Q....","......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......"],["...Q....",".......Q","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."],["...Q....",".......Q","Q.......","....Q...","......Q.",".Q......",".....Q..","..Q....."],["...Q....",".......Q","....Q...","..Q.....","Q.......","......Q.",".Q......",".....Q.."],["....Q...","Q.......","...Q....",".....Q..",".......Q",".Q......","......Q.","..Q....."],["....Q...","Q.......",".......Q","...Q....",".Q......","......Q.","..Q.....",".....Q.."],["....Q...","Q.......",".......Q",".....Q..","..Q.....","......Q.",".Q......","...Q...."],["....Q...",".Q......","...Q....",".....Q..",".......Q","..Q.....","Q.......","......Q."],["....Q...",".Q......","...Q....","......Q.","..Q.....",".......Q",".....Q..","Q......."],["....Q...",".Q......",".....Q..","Q.......","......Q.","...Q....",".......Q","..Q....."],["....Q...",".Q......",".......Q","Q.......","...Q....","......Q.","..Q.....",".....Q.."],["....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q....","......Q."],["....Q...","..Q.....","Q.......","......Q.",".Q......",".......Q",".....Q..","...Q...."],["....Q...","..Q.....",".......Q","...Q....","......Q.","Q.......",".....Q..",".Q......"],["....Q...","......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......"],["....Q...","......Q.","Q.......","...Q....",".Q......",".......Q",".....Q..","..Q....."],["....Q...","......Q.",".Q......","...Q....",".......Q","Q.......","..Q.....",".....Q.."],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q"],["....Q...","......Q.",".Q......",".....Q..","..Q.....","Q.......",".......Q","...Q...."],["....Q...","......Q.","...Q....","Q.......","..Q.....",".......Q",".....Q..",".Q......"],["....Q...",".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q."],["....Q...",".......Q","...Q....","Q.......","......Q.",".Q......",".....Q..","..Q....."],[".....Q..","Q.......","....Q...",".Q......",".......Q","..Q.....","......Q.","...Q...."],[".....Q..",".Q......","......Q.","Q.......","..Q.....","....Q...",".......Q","...Q...."],[".....Q..",".Q......","......Q.","Q.......","...Q....",".......Q","....Q...","..Q....."],[".....Q..","..Q.....","Q.......","......Q.","....Q...",".......Q",".Q......","...Q...."],[".....Q..","..Q.....","Q.......",".......Q","...Q....",".Q......","......Q.","....Q..."],[".....Q..","..Q.....","Q.......",".......Q","....Q...",".Q......","...Q....","......Q."],[".....Q..","..Q.....","....Q...","......Q.","Q.......","...Q....",".Q......",".......Q"],[".....Q..","..Q.....","....Q...",".......Q","Q.......","...Q....",".Q......","......Q."],[".....Q..","..Q.....","......Q.",".Q......","...Q....",".......Q","Q.......","....Q..."],[".....Q..","..Q.....","......Q.",".Q......",".......Q","....Q...","Q.......","...Q...."],[".....Q..","..Q.....","......Q.","...Q....","Q.......",".......Q",".Q......","....Q..."],[".....Q..","...Q....","Q.......","....Q...",".......Q",".Q......","......Q.","..Q....."],[".....Q..","...Q....",".Q......",".......Q","....Q...","......Q.","Q.......","..Q....."],[".....Q..","...Q....","......Q.","Q.......","..Q.....","....Q...",".Q......",".......Q"],[".....Q..","...Q....","......Q.","Q.......",".......Q",".Q......","....Q...","..Q....."],[".....Q..",".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q....."],["......Q.","Q.......","..Q.....",".......Q",".....Q..","...Q....",".Q......","....Q..."],["......Q.",".Q......","...Q....","Q.......",".......Q","....Q...","..Q.....",".....Q.."],["......Q.",".Q......",".....Q..","..Q.....","Q.......","...Q....",".......Q","....Q..."],["......Q.","..Q.....","Q.......",".....Q..",".......Q","....Q...",".Q......","...Q...."],["......Q.","..Q.....",".......Q",".Q......","....Q...","Q.......",".....Q..","...Q...."],["......Q.","...Q....",".Q......","....Q...",".......Q","Q.......","..Q.....",".....Q.."],["......Q.","...Q....",".Q......",".......Q",".....Q..","Q.......","..Q.....","....Q..."],["......Q.","....Q...","..Q.....","Q.......",".....Q..",".......Q",".Q......","...Q...."],[".......Q",".Q......","...Q....","Q.......","......Q.","....Q...","..Q.....",".....Q.."],[".......Q",".Q......","....Q...","..Q.....","Q.......","......Q.","...Q....",".....Q.."],[".......Q","..Q.....","Q.......",".....Q..",".Q......","....Q...","......Q.","...Q...."],[".......Q","...Q....","Q.......","..Q.....",".....Q..",".Q......","......Q.","....Q..."]]
         elif n == 9:
             return [["Q........","..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q...."],["Q........","..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","...Q.....",".....Q..."],["Q........","..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q....."],["Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q....","......Q.."],["Q........","...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q.."],["Q........","...Q.....",".....Q...",".......Q.",".Q.......","....Q....","..Q......","........Q","......Q.."],["Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q..."],["Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q...","..Q......"],["Q........","...Q.....",".......Q.","..Q......","........Q","......Q..","....Q....",".Q.......",".....Q..."],["Q........","....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q.."],["Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q.....",".......Q."],["Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q..."],["Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......"],["Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["Q........","....Q....","........Q",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","......Q.."],["Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......","....Q...."],["Q........",".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q."],["Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q...."],["Q........",".....Q...",".......Q.","..Q......","......Q..","...Q.....",".Q.......","........Q","....Q...."],["Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......"],["Q........",".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q....."],["Q........","......Q..","...Q.....",".....Q...","........Q",".Q.......","....Q....","..Q......",".......Q."],["Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q.......",".....Q..."],["Q........","......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q...."],["Q........","......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q....."],["Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......","....Q...."],["Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q.......","...Q.....","......Q.."],["Q........",".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q..."],[".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q....",".......Q."],[".Q.......","...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....",".......Q.","..Q......","........Q",".....Q...","Q........","....Q....","......Q.."],[".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q.","....Q...."],[".Q.......","...Q.....","........Q","......Q..","....Q....","..Q......","Q........",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q.....","........Q"],[".Q.......","....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q."],[".Q.......","....Q....","......Q..","........Q","..Q......",".....Q...","...Q.....","Q........",".......Q."],[".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q..."],[".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q..","...Q....."],[".Q.......","....Q....",".......Q.","Q........","........Q",".....Q...","..Q......","......Q..","...Q....."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q.."],[".Q.......","....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q....."],[".Q.......","....Q....","........Q","...Q.....","Q........",".......Q.",".....Q...","..Q......","......Q.."],[".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q.","....Q...."],[".Q.......",".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q"],[".Q.......",".....Q...","Q........","......Q..","....Q....","..Q......","........Q","...Q.....",".......Q."],[".Q.......",".....Q...","Q........","........Q","....Q....",".......Q.","...Q.....","......Q..","..Q......"],[".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q...."],[".Q.......",".....Q...","........Q","..Q......","....Q....",".......Q.","...Q.....","Q........","......Q.."],[".Q.......","......Q..","....Q....","Q........","........Q","...Q.....",".....Q...",".......Q.","..Q......"],[".Q.......","......Q..","....Q....",".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q"],[".Q.......","......Q..","........Q",".....Q...","..Q......","Q........","...Q.....",".......Q.","....Q...."],[".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......","....Q...."],[".Q.......",".......Q.","....Q....","..Q......","........Q",".....Q...","...Q.....","Q........","......Q.."],[".Q.......",".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q...."],[".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q..."],[".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....","......Q.."],[".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q.","....Q...."],[".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........","..Q......","....Q....",".......Q."],["..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.",".....Q..."],["..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q","......Q.."],["..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q","....Q...."],["..Q......","Q........","......Q..","....Q....",".......Q.",".Q.......","...Q.....",".....Q...","........Q"],["..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q.......",".....Q..."],["..Q......","Q........","........Q","......Q..","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q..."],["..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q...","........Q"],["..Q......","....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q"],["..Q......","....Q....",".......Q.",".Q.......","........Q",".....Q...","Q........","......Q..","...Q....."],["..Q......","....Q....",".......Q.",".Q.......","........Q","......Q..","Q........","...Q.....",".....Q..."],["..Q......","....Q....","........Q",".Q.......","...Q.....","......Q..","Q........",".......Q.",".....Q..."],["..Q......","....Q....","........Q","...Q.....","Q........","......Q..",".Q.......",".....Q...",".......Q."],["..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q....","........Q"],["..Q......",".....Q...",".Q.......","........Q","....Q....","Q........",".......Q.","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q"],["..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q.."],["..Q......",".....Q...",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........"],["..Q......",".....Q...",".......Q.","....Q....","Q........","........Q","......Q..",".Q.......","...Q....."],["..Q......",".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........"],["..Q......",".....Q...","........Q","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],["..Q......",".....Q...","........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q."],["..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q..","....Q...."],["..Q......",".....Q...","........Q","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q.."],["..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],["..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q...."],["..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q...."],["..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q",".....Q..."],["..Q......","......Q..",".Q.......",".......Q.","....Q....","........Q","Q........",".....Q...","...Q....."],["..Q......","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","Q........","....Q....","........Q"],["..Q......","......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q..."],["..Q......","......Q..","...Q.....",".Q.......","........Q",".....Q...","Q........","....Q....",".......Q."],["..Q......","......Q..","...Q.....",".......Q.","....Q....","........Q","Q........",".....Q...",".Q......."],["..Q......","......Q..","........Q","Q........","....Q....",".Q.......",".......Q.",".....Q...","...Q....."],["..Q......","......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........"],["..Q......",".......Q.",".Q.......","...Q.....","........Q","......Q..","....Q....","Q........",".....Q..."],["..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......","....Q....","Q........",".....Q..."],["..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],["..Q......",".......Q.",".....Q...","...Q.....","........Q","Q........","....Q....","......Q..",".Q......."],["..Q......",".......Q.",".....Q...","........Q",".Q.......","....Q....","Q........","...Q.....","......Q.."],["..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["..Q......","........Q","...Q.....","Q........",".......Q.",".....Q...",".Q.......","......Q..","....Q...."],["..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q..","....Q...."],["..Q......","........Q","...Q.....",".......Q.","....Q....",".Q.......",".....Q...","Q........","......Q.."],["..Q......","........Q",".....Q...",".Q.......","....Q....","......Q..","Q........","...Q.....",".......Q."],["..Q......","........Q",".....Q...","...Q.....","Q........","......Q..","....Q....",".Q.......",".......Q."],["..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q...."],["...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q....","......Q.."],["...Q.....","Q........","....Q....",".Q.......","........Q","......Q..","..Q......",".......Q.",".....Q..."],["...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q"],["...Q.....","Q........","....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","......Q.."],["...Q.....","Q........","......Q..","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["...Q.....","Q........","........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q...."],["...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q","......Q.."],["...Q.....",".Q.......","......Q..","..Q......","Q........",".......Q.","....Q....","........Q",".....Q..."],["...Q.....",".Q.......","......Q..","........Q","Q........","....Q....",".......Q.",".....Q...","..Q......"],["...Q.....",".Q.......","......Q..","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........",".....Q..."],["...Q.....",".Q.......","........Q","..Q......",".....Q...",".......Q.","Q........","....Q....","......Q.."],["...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......","......Q.."],["...Q.....",".....Q...","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q"],["...Q.....",".....Q...","Q........","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......"],["...Q.....",".....Q...","Q........","........Q","......Q..","..Q......",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q.."],["...Q.....",".....Q...","..Q......","........Q",".Q.......",".......Q.","....Q....","......Q..","Q........"],["...Q.....",".....Q...","..Q......","........Q","......Q..","Q........",".......Q.",".Q.......","....Q...."],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","Q........","........Q","......Q..","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","....Q....","......Q..","........Q","Q........","..Q......"],["...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q"],["...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q.......","........Q"],["...Q.....",".....Q...","........Q","..Q......","Q........",".......Q.",".Q.......","....Q....","......Q.."],["...Q.....","......Q..","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","Q........",".....Q...","........Q",".Q.......",".......Q.","....Q....","..Q......"],["...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q..."],["...Q.....","......Q..","..Q......",".....Q...","........Q","Q........",".......Q.","....Q....",".Q......."],["...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q....","........Q",".....Q...","Q........"],["...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........","........Q",".Q.......","....Q...."],["...Q.....","......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........"],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........","..Q......",".......Q.",".....Q..."],["...Q.....","......Q..","....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......"],["...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......","Q........"],["...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q..."],["...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q."],["...Q.....","......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q......."],["...Q.....",".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q"],["...Q.....",".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q.."],["...Q.....",".......Q.","....Q....","..Q......","Q........","......Q..",".Q.......",".....Q...","........Q"],["...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q."],["...Q.....","........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","......Q.."],["...Q.....","........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q..."],["...Q.....","........Q","....Q....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q.."],["....Q....","Q........",".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q.."],["....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","........Q",".....Q...","..Q......"],["....Q....","Q........",".......Q.",".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q"],["....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q...",".......Q."],["....Q....",".Q.......","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".......Q."],["....Q....",".Q.......",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".......Q."],["....Q....",".Q.......",".....Q...","........Q","..Q......",".......Q.","...Q.....","......Q..","Q........"],["....Q....",".Q.......",".....Q...","........Q","......Q..","...Q.....","Q........","..Q......",".......Q."],["....Q....",".Q.......",".......Q.","Q........","...Q.....","......Q..","........Q",".....Q...","..Q......"],["....Q....",".Q.......",".......Q.","Q........","......Q..","........Q","..Q......",".....Q...","...Q....."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........","........Q",".....Q..."],["....Q....",".Q.......",".......Q.","..Q......","......Q..","........Q","Q........",".....Q...","...Q....."],["....Q....",".Q.......","........Q","Q........",".....Q...",".......Q.","..Q......","......Q..","...Q....."],["....Q....",".Q.......","........Q",".....Q...","..Q......","......Q..","...Q.....","Q........",".......Q."],["....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q.....",".......Q."],["....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q..","........Q"],["....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q.....","........Q"],["....Q....","..Q......",".....Q...","........Q",".Q.......",".......Q.","Q........","...Q.....","......Q.."],["....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q.......",".......Q."],["....Q....","..Q......",".....Q...","........Q","......Q..",".Q.......","...Q.....",".......Q.","Q........"],["....Q....","..Q......",".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q......."],["....Q....","..Q......",".......Q.","...Q.....",".Q.......","........Q",".....Q...","Q........","......Q.."],["....Q....","..Q......",".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........"],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","Q........","...Q.....","......Q.."],["....Q....","..Q......",".......Q.",".....Q...",".Q.......","........Q","......Q..","Q........","...Q....."],["....Q....","..Q......","........Q","...Q.....",".Q.......",".......Q.",".....Q...","Q........","......Q.."],["....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q.."],["....Q....","......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......"],["....Q....","......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......"],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","..Q......","........Q",".....Q..."],["....Q....","......Q..",".Q.......","...Q.....",".......Q.","Q........","........Q",".....Q...","..Q......"],["....Q....","......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q"],["....Q....","......Q..",".Q.......",".....Q...",".......Q.","Q........","...Q.....","........Q","..Q......"],["....Q....","......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q."],["....Q....","......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q"],["....Q....","......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.",".Q......."],["....Q....","......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......"],["....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........"],["....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.",".....Q...","..Q......","Q........"],["....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q......."],["....Q....",".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q......."],["....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........","........Q","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q...","........Q","Q........","...Q....."],["....Q....",".......Q.",".Q.......","........Q","..Q......","Q........","......Q..","...Q.....",".....Q..."],["....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q.."],["....Q....",".......Q.","...Q.....","Q........","..Q......",".....Q...","........Q","......Q..",".Q......."],["....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......","........Q"],["....Q....",".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q......."],["....Q....",".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q......."],["....Q....",".......Q.",".....Q...","........Q","..Q......","Q........","......Q..","...Q.....",".Q......."],["....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......",".......Q.",".....Q...","Q........"],["....Q....","........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q.."],["....Q....","........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......"],[".....Q...","Q........","....Q....",".Q.......","........Q","......Q..","...Q.....",".......Q.","..Q......"],[".....Q...","Q........","....Q....","......Q..","........Q","..Q......",".......Q.",".Q.......","...Q....."],[".....Q...","Q........","....Q....","......Q..","........Q","...Q.....",".Q.......",".......Q.","..Q......"],[".....Q...","Q........","......Q..","...Q.....",".......Q.","..Q......","....Q....","........Q",".Q......."],[".....Q...",".Q.......","....Q....","......Q..","........Q","..Q......",".......Q.","...Q.....","Q........"],[".....Q...",".Q.......","....Q....","......Q..","........Q","...Q.....",".......Q.","Q........","..Q......"],[".....Q...",".Q.......","........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........"],[".....Q...","..Q......","Q........","...Q.....","......Q..","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","Q........",".......Q.","...Q.....","........Q","......Q..","....Q....",".Q......."],[".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q....."],[".....Q...","..Q......","....Q....",".......Q.","Q........","...Q.....",".Q.......","......Q..","........Q"],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","...Q.....",".Q.......","......Q.."],[".....Q...","..Q......","....Q....",".......Q.","Q........","........Q","......Q..",".Q.......","...Q....."],[".....Q...","..Q......","......Q..",".Q.......","...Q.....",".......Q.","Q........","....Q....","........Q"],[".....Q...","..Q......","......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q...."],[".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q.....","........Q"],[".....Q...","..Q......","......Q..","...Q.....","Q........","........Q",".Q.......","....Q....",".......Q."],[".....Q...","..Q......","........Q",".Q.......","....Q....",".......Q.","Q........","......Q..","...Q....."],[".....Q...","..Q......","........Q","...Q.....","Q........",".......Q.",".Q.......","....Q....","......Q.."],[".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q....",".......Q."],[".....Q...","...Q.....","Q........","......Q..","........Q",".Q.......",".......Q.","....Q....","..Q......"],[".....Q...","...Q.....",".Q.......","......Q..","........Q","..Q......","....Q....",".......Q.","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","..Q......","........Q","......Q..","....Q....","Q........"],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","..Q......","Q........","........Q","......Q.."],[".....Q...","...Q.....",".Q.......",".......Q.","....Q....","........Q","Q........","..Q......","......Q.."],[".....Q...","...Q.....","......Q..","Q........","..Q......","........Q",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......","........Q"],[".....Q...","...Q.....","......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......"],[".....Q...","...Q.....","........Q","Q........","..Q......","......Q..",".Q.......",".......Q.","....Q...."],[".....Q...","...Q.....","........Q","Q........","....Q....",".Q.......",".......Q.","..Q......","......Q.."],[".....Q...","...Q.....","........Q","....Q....",".......Q.",".Q.......","......Q..","..Q......","Q........"],[".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".....Q...",".......Q.","Q........","......Q..","...Q.....",".Q.......","........Q","....Q....","..Q......"],[".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q....","........Q","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q",".Q.......","....Q....","......Q..","...Q....."],[".....Q...",".......Q.","..Q......","Q........","........Q","....Q....",".Q.......","...Q.....","......Q.."],[".....Q...",".......Q.","..Q......","......Q..","........Q",".Q.......","....Q....","Q........","...Q....."],[".....Q...",".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......"],[".....Q...","........Q","Q........","...Q.....","......Q..","..Q......",".......Q.",".Q.......","....Q...."],[".....Q...","........Q","..Q......","Q........",".......Q.","...Q.....",".Q.......","......Q..","....Q...."],[".....Q...","........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......"],[".....Q...","........Q","....Q....",".Q.......",".......Q.","..Q......","......Q..","...Q.....","Q........"],[".....Q...","........Q","....Q....",".......Q.","Q........","..Q......","......Q..",".Q.......","...Q....."],[".....Q...","........Q","......Q..","...Q.....","Q........",".......Q.",".Q.......","....Q....","..Q......"],["......Q..","Q........","...Q.....",".Q.......",".......Q.",".....Q...","........Q","..Q......","....Q...."],["......Q..","Q........","...Q.....",".....Q...","........Q","..Q......","....Q....",".......Q.",".Q......."],["......Q..","Q........","...Q.....",".......Q.","....Q....","..Q......","........Q",".....Q...",".Q......."],["......Q..","Q........",".....Q...",".Q.......","....Q....",".......Q.","...Q.....","........Q","..Q......"],["......Q..","Q........",".....Q...",".......Q.",".Q.......","...Q.....","........Q","..Q......","....Q...."],["......Q..","Q........",".....Q...","........Q",".Q.......","...Q.....",".......Q.","..Q......","....Q...."],["......Q..","Q........",".......Q.","....Q....",".Q.......","........Q","..Q......",".....Q...","...Q....."],["......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","........Q",".....Q...","..Q......"],["......Q..",".Q.......","...Q.....",".....Q...","Q........","........Q","....Q....","..Q......",".......Q."],["......Q..",".Q.......","...Q.....","........Q","Q........",".......Q.","....Q....","..Q......",".....Q..."],["......Q..",".Q.......",".....Q...","..Q......","Q........",".......Q.","....Q....","........Q","...Q....."],["......Q..",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q","...Q....."],["......Q..","..Q......","Q........",".....Q...",".......Q.","....Q....",".Q.......","...Q.....","........Q"],["......Q..","..Q......","Q........","........Q","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","..Q......",".....Q...",".Q.......","....Q....","Q........","........Q","...Q.....",".......Q."],["......Q..","..Q......",".....Q...",".......Q.","Q........","...Q.....","........Q","....Q....",".Q......."],["......Q..","..Q......",".....Q...",".......Q.","Q........","....Q....","........Q",".Q.......","...Q....."],["......Q..","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","........Q","....Q....","Q........"],["......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........","........Q","...Q.....",".....Q..."],["......Q..","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q....","Q........","...Q....."],["......Q..","...Q.....","Q........","..Q......",".....Q...","........Q",".Q.......",".......Q.","....Q...."],["......Q..","...Q.....","Q........","..Q......",".......Q.",".....Q...",".Q.......","........Q","....Q...."],["......Q..","...Q.....","Q........","..Q......","........Q",".....Q...",".......Q.","....Q....",".Q......."],["......Q..","...Q.....","Q........","....Q....",".Q.......","........Q",".....Q...",".......Q.","..Q......"],["......Q..","...Q.....","Q........",".......Q.",".Q.......","........Q",".....Q...","..Q......","....Q...."],["......Q..","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q...","........Q",".Q......."],["......Q..","...Q.....","Q........","........Q",".Q.......",".....Q...",".......Q.","..Q......","....Q...."],["......Q..","...Q.....",".Q.......","....Q....",".......Q.","Q........","..Q......",".....Q...","........Q"],["......Q..","...Q.....",".Q.......","....Q....","........Q","Q........","..Q......",".......Q.",".....Q..."],["......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q....","........Q"],["......Q..","...Q.....",".Q.......","........Q","....Q....","Q........",".......Q.",".....Q...","..Q......"],["......Q..","...Q.....",".Q.......","........Q",".....Q...","..Q......","....Q....",".......Q.","Q........"],["......Q..","...Q.....",".......Q.","Q........","....Q....","........Q",".Q.......",".....Q...","..Q......"],["......Q..","...Q.....",".......Q.","..Q......","........Q",".....Q...",".Q.......","....Q....","Q........"],["......Q..","....Q....","Q........",".....Q...","........Q","..Q......",".......Q.","...Q.....",".Q......."],["......Q..","....Q....","Q........",".......Q.",".....Q...","..Q......","........Q",".Q.......","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","..Q......","........Q",".....Q...","...Q....."],["......Q..","....Q....",".Q.......",".......Q.","Q........","...Q.....","........Q","..Q......",".....Q..."],["......Q..","....Q....","..Q......","........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q","..Q......",".....Q...","...Q.....","Q........"],["......Q..","....Q....",".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q....."],["......Q..","........Q","Q........","..Q......","....Q....",".......Q.",".Q.......","...Q.....",".....Q..."],["......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q....",".......Q.","...Q....."],["......Q..","........Q","..Q......","....Q....",".Q.......",".......Q.",".....Q...","...Q.....","Q........"],["......Q..","........Q","..Q......",".......Q.",".Q.......","...Q.....",".....Q...","Q........","....Q...."],["......Q..","........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......"],["......Q..","........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q....."],[".......Q.","Q........","...Q.....",".....Q...","..Q......","........Q","......Q..","....Q....",".Q......."],[".......Q.","Q........","...Q.....","......Q..","..Q......",".....Q...","........Q",".Q.......","....Q...."],[".......Q.","Q........","...Q.....","......Q..","....Q....",".Q.......","........Q",".....Q...","..Q......"],[".......Q.","Q........","....Q....","......Q..",".Q.......",".....Q...","..Q......","........Q","...Q....."],[".......Q.",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......","....Q...."],[".......Q.",".Q.......","....Q....","......Q..","Q........","...Q.....",".....Q...","........Q","..Q......"],[".......Q.",".Q.......","........Q",".....Q...","..Q......","Q........","...Q.....","......Q..","....Q...."],[".......Q.","..Q......","Q........","...Q.....","......Q..","........Q",".....Q...",".Q.......","....Q...."],[".......Q.","..Q......","....Q....",".Q.......","........Q",".....Q...","...Q.....","......Q..","Q........"],[".......Q.","..Q......","....Q....","........Q","Q........",".....Q...","...Q.....",".Q.......","......Q.."],[".......Q.","...Q.....","Q........","......Q..","....Q....",".Q.......",".....Q...","........Q","..Q......"],[".......Q.","...Q.....","......Q..","........Q",".Q.......",".....Q...","Q........","..Q......","....Q...."],[".......Q.","...Q.....","........Q","Q........","....Q....",".Q.......",".....Q...","..Q......","......Q.."],[".......Q.","...Q.....","........Q","..Q......","....Q....","......Q..","Q........",".....Q...",".Q......."],[".......Q.","...Q.....","........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........"],[".......Q.","...Q.....","........Q","......Q..","..Q......","Q........",".....Q...",".Q.......","....Q...."],[".......Q.","....Q....","Q........",".....Q...","........Q",".Q.......","...Q.....","......Q..","..Q......"],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","...Q.....","Q........","......Q..","........Q",".....Q...","..Q......"],[".......Q.","....Q....",".Q.......","........Q","Q........","...Q.....","......Q..","..Q......",".....Q..."],[".......Q.","....Q....",".Q.......","........Q","......Q..","...Q.....","Q........","..Q......",".....Q..."],[".......Q.","....Q....","..Q......","Q........",".....Q...",".Q.......","........Q","......Q..","...Q....."],[".......Q.","....Q....","..Q......","Q........","......Q..","...Q.....",".....Q...","........Q",".Q......."],[".......Q.","....Q....","..Q......",".....Q...","........Q","......Q..","Q........","...Q.....",".Q......."],[".......Q.","....Q....","..Q......","........Q","......Q..",".Q.......","...Q.....",".....Q...","Q........"],[".......Q.",".....Q...","Q........","..Q......","....Q....","......Q..","........Q","...Q.....",".Q......."],[".......Q.",".....Q...","Q........","..Q......","......Q..","........Q","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...",".Q.......","......Q..","Q........","...Q.....","........Q","....Q....","..Q......"],[".......Q.",".....Q...","..Q......","........Q","......Q..","Q........","...Q.....",".Q.......","....Q...."],[".......Q.",".....Q...","........Q","..Q......","Q........","...Q.....","......Q..","....Q....",".Q......."],["........Q",".Q.......","....Q....","......Q..","Q........","..Q......",".......Q.",".....Q...","...Q....."],["........Q",".Q.......","....Q....","......Q..","...Q.....","Q........",".......Q.",".....Q...","..Q......"],["........Q",".Q.......",".....Q...",".......Q.","..Q......","Q........","...Q.....","......Q..","....Q...."],["........Q","..Q......","....Q....",".Q.......",".......Q.","Q........","......Q..","...Q.....",".....Q..."],["........Q","..Q......",".....Q...",".Q.......","......Q..","Q........","...Q.....",".......Q.","....Q...."],["........Q","..Q......",".....Q...",".Q.......","......Q..","....Q....","Q........",".......Q.","...Q....."],["........Q","..Q......",".....Q...","...Q.....","Q........",".......Q.","....Q....","......Q..",".Q......."],["........Q","...Q.....","Q........","....Q....",".......Q.",".Q.......","......Q..","..Q......",".....Q..."],["........Q","...Q.....",".Q.......","....Q....",".......Q.",".....Q...","Q........","..Q......","......Q.."],["........Q","...Q.....",".Q.......","......Q..","..Q......",".....Q...",".......Q.","Q........","....Q...."],["........Q","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","Q........","..Q......","....Q...."],["........Q","...Q.....",".....Q...",".......Q.","..Q......","Q........","......Q..","....Q....",".Q......."],["........Q","...Q.....",".......Q.","Q........","..Q......",".....Q...",".Q.......","......Q..","....Q...."],["........Q","....Q....","Q........","...Q.....",".....Q...",".......Q.",".Q.......","......Q..","..Q......"],["........Q","....Q....","Q........",".......Q.","...Q.....",".Q.......","......Q..","..Q......",".....Q..."],["........Q","....Q....","..Q......","Q........",".....Q...",".......Q.",".Q.......","...Q.....","......Q.."],["........Q","....Q....","..Q......","Q........","......Q..",".Q.......",".......Q.",".....Q...","...Q....."],["........Q","....Q....","..Q......",".......Q.","...Q.....","......Q..","Q........",".....Q...",".Q......."],["........Q","....Q....",".......Q.","...Q.....","Q........","......Q..",".Q.......",".....Q...","..Q......"],["........Q",".....Q...",".Q.......","......Q..","Q........","..Q......","....Q....",".......Q.","...Q....."],["........Q",".....Q...","..Q......","Q........",".......Q.","....Q....",".Q.......","...Q.....","......Q.."],["........Q",".....Q...","..Q......","......Q..",".Q.......",".......Q.","....Q....","Q........","...Q....."],["........Q",".....Q...","...Q.....",".Q.......",".......Q.","....Q....","......Q..","Q........","..Q......"],["........Q",".....Q...","...Q.....","......Q..","Q........",".......Q.",".Q.......","....Q....","..Q......"],["........Q",".....Q...",".......Q.",".Q.......","...Q.....","Q........","......Q..","....Q....","..Q......"],["........Q","......Q..",".Q.......","...Q.....","Q........",".......Q.","....Q....","..Q......",".....Q..."],["........Q","......Q..","..Q......",".......Q.",".Q.......","....Q....","Q........",".....Q...","...Q....."],["........Q","......Q..","...Q.....",".Q.......",".......Q.",".....Q...","Q........","..Q......","....Q...."]]

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         def dfs(queens, xy_dif, xy_sum):
             p = len(queens)
             if p == n:
                 res.append(queens)
                 return
             for i in range(n):
                 if i not in queens and p - i not in xy_dif and p + i not in xy_sum:
                     dfs(queens + [i], xy_dif + [p - i], xy_sum + [p + i])
         res = []                    
         dfs([], [], [])
         return [["." * i + "Q"  + '.' * (n - i - 1) for i in sol] for sol in res]

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         ans = []
         def dfs(queens, xy_dif, xy_sum):
             p = len(queens)
             if p == n:
                 result.append(queens)
                 return None
 
             for q in range(n):
                 if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
                     dfs(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
 
         result = []
         dfs([], [], [])
         return [["."*i+"Q"+"."*(n-i-1) for i in sol] for sol in result]

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         def dfs(cols, diag_45, diag_135, depth=0):
             #print(' ' * depth, 'cols =', cols, 'diag_45 =', diag_45, 'diag_135 =', diag_135)
             row = len(cols)
             if row == n:
                 result.append(cols)
                 #print(' '*depth, 'Found placement!')
                 return 
             for col in range(n):
                 if col not in cols and (row - col) not in diag_45 and (row + col) not in diag_135:
                     dfs(cols + [col], diag_45 + [row - col], diag_135 + [row + col], depth + 1)
             else:
                 pass
                 #print(' ' * depth, 'Placement not found; backtrack...')
 
         result = []
         dfs([],[],[])
         return [ ['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in result]

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
 
         result = [];
         visits = [0, 0, 0];
         board = [["." for j in range(n)] for i in range(n)];
         
         self.find(visits, n, 0, board, result);
         
         return result + [[row[ : : -1] for row in board] for board in result if n & 1 == 0 or n & 1 == 1 and board[0][n >> 1] != "Q"];
         
     def find(self, visits, n, k, board, result):
         if k >= n:
             result.append(["".join(x for x in row) for row in board]);
             return;
 
         for j in range(n if k > 0 else n + 1 >> 1):
             if self.isInvalid(visits, k, j, n):
                 continue;
                 
             self.toggleVisit(visits, k, j, n);
             board[k][j] = "Q";
             self.find(visits, n, k + 1, board, result);
             self.toggleVisit(visits, k, j, n);
             board[k][j] = ".";
     
     def toggleVisit(self, visits, i, j, n):
         visits[0] ^= 1 << j;
         visits[1] ^= 1 << i - j + n - 1;
         visits[2] ^= 1 << i + j;
         
     def isInvalid(self, visits, i, j, n):
         return visits[0] & (1 << j) > 0 or visits[1] & (1 << i - j + n - 1) > 0 or visits[2] & (1 << i + j) > 0;

class Solution:
     
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         def dfs(n, a, b, c, ans, d):
             if n==0:
                 ans = ans.append([i*'.'+'Q'+(len(a)-i-1)*'.' for i in d])
                 return None
 
             for i in range(len(a)):
                 if a[i] or b[n-1+i] or c[len(a)-1-i+n-1]: continue
                 a[i], b[n-1+i], c[len(a)-1-i+n-1] = True, True, True
                 d[n-1]=i
                 dfs(n-1, a, b, c, ans, d)
                 a[i], b[n-1+i], c[len(a)-1-i+n-1] = False, False, False
 
             return None
         a=[False for i in range(n)]
         b=[False for i in range(n*2-1)]
         c=[False for i in range(n*2-1)]
         d=[0 for i in range(n)]
         ans=[]
         dfs(n, a, b, c, ans, d)
         return ans
 
     
 


class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         row = [x for x in range(n)]
         table = []
         for i in range(n):
             table.append(row.copy())
         result = self.solve(table,0)
         result_str=[]
         for x in result:
             table_str = []
             for y in x:
                 table_str.append("."*y+"Q"+"."*(n-y-1))
             result_str.append(table_str)
         return result_str
     def solve(self,table,n):
         if table[n]==[]:return []
         elif n==len(table)-1:
             table[n] = table[n][0]
             return [table]
         else:
             result=[]
             for x in table[n]:
                 table1 = [(x if type(x)==int else x.copy()) for x in table]
                 table1[n] = x
                 for row in range(n+1,len(table)):
                     if x in table1[row]:
                         table1[row].remove(x)
                     if x+row-n in table1[row]:
                         table1[row].remove(x+row-n)
                     if x-(row-n) in table1[row]:
                         table1[row].remove(x-(row-n))
                 result.extend(self.solve(table1,n+1))
             return result

class Solution:
     def __init__(self):
         self.result = []
         self.visited = None
 
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         self.visited = [0 for i in range(n)]
         self.__solve_n_queues(n, 0, [])
         return self.result
 
     @staticmethod
     def __not_diagonal(x, y, curr_answer):
         for c_x, c_y in enumerate(curr_answer):
             if abs(c_x - x) == abs(c_y - y):
                 return False
         return True
 
     @staticmethod
     def visualize(curr_answer, n):
         answer = []
         for pos in curr_answer:
             answer.append('.' * pos + 'Q' + '.' * (n - pos - 1))
         return answer
 
     def __solve_n_queues(self, n, level, curr_answer):
         if level == n:
             self.result.append(Solution.visualize(curr_answer, n))
             return
 
         for i in range(n):
             if not self.visited[i] and Solution.__not_diagonal(level, i, curr_answer):
                 self.visited[i] = 1
                 curr_answer.append(i)
                 self.__solve_n_queues(n, level + 1, curr_answer)
                 curr_answer.pop()
                 self.visited[i] = 0

class Solution:
     def solveNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         queens = []
         res = []
         def backtracking(n, k, queens):
             if k > n:
                 return
             elif len(queens) == n and k < n:
                 return
             elif len(queens) == n and k == n:
                 temp = queens[:]                
                 res.append(temp)
             else:
                 row =[0] * n
                 temp_q = queens[:]
                 for each in  temp_q:
                     x, y = each[0], each[1]
                     
                     row[y] = 1
                     if y + k - x < n:
                         row[y + k - x] = 1
                     if y - k + x >= 0:
                         row[y - k + x] = 1
                 
                 for i in range(n):
                     if row[i] == 0:
                         temp_q.append((k,i))
                         # print(temp_q)
                         backtracking(n, k + 1, temp_q)
                         temp_q.pop()
                 
                 
                 
         backtracking(n, 0, queens)
         
         layout = []
         for q in res:
             temp = []
             for each in q:
                 _row = "." * each[1] + "Q" + "." * (n - each[1] - 1)
                 temp.append(_row)
             layout.append(temp)
         return layout