N-Queens Problem

Mô tả

Xếp n quân hậu lên bàn cờ n×n sao cho không quân hậu nào ăn nhau. In một cách xếp hoặc "No solution" nếu không có.

Input Format

Một dòng chứa số nguyên n.

Constraints

1 ≤ n ≤ 10

Sample Input

4

Sample Output

. Q . .
. . . Q
Q . . .
. . Q .