루크 배치하기

체스에서 루크(rook)는 가로 또는 세로 방향으로 원하는 만큼 이동할 수 있는 기물이다. 이 문제에서는 루크가 통과할 수 없는 벽이 놓일 수 있는 작은 체스판(최대 4×4)을 다룬다. 목표는 어떤 두 루크도 서로를 잡을 수 없도록 판 위에 가능한 한 많은 루크를 놓는 것이다. 같은 행 또는 같은 열에 있는 두 루크는 그 사이에 벽이 하나도 없을 때에만 서로 잡을 수 있으며, 그런 쌍이 존재하는 배치는 불법(illegal)이다. 사이에 벽이 하나 이상 있으면 서로 잡을 수 없다.

아래 그림은 같은 판을 다섯 가지로 보여 준다. 첫 번째는 빈 판이고, 두 번째와 세 번째는 합법적인(legal) 배치, 네 번째와 다섯 번째는 불법적인 배치이다. 이 판에서 합법적인 배치로 놓을 수 있는 루크의 최대 개수는 5이며, 두 번째 그림이 그 한 예이다(다른 방법도 여럿 있다).

판의 정보가 주어졌을 때, 합법적인 배치로 놓을 수 있는 루크의 최대 개수를 계산하는 프로그램을 작성하라.

입력은 하나 이상의 판 정보로 이루어지며, 파일의 끝은 숫자 0이 적힌 한 줄로 표시된다. 각 판 정보는 판의 크기인 양의 정수 $n$이 적힌 줄로 시작한다($n \le 4$). 그 다음 $n$개의 줄이 각각 판의 한 행을 나타내며, '.'은 빈 칸을, 대문자 'X'는 벽을 의미한다. 입력에는 공백이 없다.

각 판마다 합법적인 배치로 놓을 수 있는 루크의 최대 개수를 한 줄에 하나씩 출력한다.