무적여왕

양의 정수 n을 입력 받아 n x n 체스보드에 n개의 여왕을 서로 공격할 수 없도록 배치하는 함수를 작성하세요.

서로 공격할 수 없도록 배치하는 것은, 한 여왕이 한번에 상대편의 여왕을 공격 할 수 없도록 배치하는 것을 의미합니다. 즉, 한 공격에 상대편의 여왕이 있는 위치로 이동할 수 없는 배치입니다.

체스에서 여왕은 한 턴에서 수평, 수직 또는 대각선으로 이동할 수 있습니다.

위의 체스판은 4x4 체스판에 4개의 여왕이 서로 공격할 수 없도록 배치된 예입니다. 참고로 4x4 체스판에는 4명의 여왕이 서로 공격할 수 없도록 하는 배치가 딱 2개 있습니다.

예제 1

입력

n = 4

출력

2