#1970 N Queen

1 s   128 MB  

Description

유명한 N Queen 문제를 풀어보자.

NxN 체스보드에 N개의 Queen을 배치시키자.

Input

입력의 첫줄에 N이 주어진다. N의 범위는 적당히 주어진다.

Output

N개의 Queen이 배치된 체스판을 출력한다.

Queen을 놓은 자리에는 Q를, 아무것도 놓이지 않은자리는 . 을 출력한다.

답이 여러개 존재하는 경우, 아무거나 출력한다.

답이 존재하지 않는 경우, -1을 출력한다

Sample Input

Sample Output

1
Q