점과 상자

앨리스와 밥이 $N \times N$ 격자 위의 점으로 점과 상자 게임을 한다. 두 사람은 번갈아 한 수씩 두고, 한 수는 가로나 세로로 이웃한 두 점 가운데 아직 이어지지 않은 쌍을 선분으로 잇는 것이다. 선분 네 개가 단위 정사각형 하나를 둘러싸면 네 번째 선분을 그은 사람이 그 정사각형으로 1점을 얻는다. 그을 수 있는 선분을 모두 그으면 게임이 끝나고, 점수가 더 많은 사람이 이긴다.

오늘 두 사람은 승부에 뜻이 없어서 특별한 전략을 따르지 않는다. 점수를 얻는 수가 있어도 그 수를 두지 않고 다른 곳에 둘 수 있다. 한참을 두었는데 아직 아무도 점수를 얻지 못했다. 이대로 아무도 점수를 얻지 못하면 두 사람은 곧 지루해진다.

현재 판이 주어진다. 정사각형을 하나도 완성하지 않으면서 더 둘 수 있는 수의 최대 개수를 $k$라고 하자. 그 $k$수를 둔 뒤에는 남은 어떤 선분을 그어도 정사각형이 완성되므로 $k + 1$번째 수에서 반드시 누군가 점수를 얻는다. 앨리스나 밥이 반드시 점수를 얻게 되기까지 최악의 경우 둘 수 있는 수의 개수 $k + 1$을 구한다.

첫째 줄에 격자 한 변의 점 개수 $N$ ($2 \le N \le 80$)이 주어진다.

다음 $2N - 1$개 줄에는 각각 $2N - 1$개의 문자가 주어지며, 현재 판의 상태를 행 우선 순서로 나타낸다. 행과 열의 번호는 $1$부터 시작한다.

• $1 \le i \le N$, $1 \le j \le N$인 칸 $(2i - 1, 2j - 1)$은 *이고 점 $(i, j)$를 나타낸다.
• $1 \le i \le N$, $1 \le j \le N - 1$인 칸 $(2i - 1, 2j)$는 점 $(i, j)$와 점 $(i, j + 1)$이 선분으로 이어져 있으면 -, 아니면 .이다.
• $1 \le i \le N - 1$, $1 \le j \le N$인 칸 $(2i, 2j - 1)$은 점 $(i, j)$와 점 $(i + 1, j)$가 선분으로 이어져 있으면 |, 아니면 .이다.
• $1 \le i \le N - 1$, $1 \le j \le N - 1$인 칸 $(2i, 2j)$는 .이다.

주어진 판에는 완성된 단위 정사각형이 없다. 즉 두 사람 모두 아직 점수를 얻지 못했다.

앨리스나 밥이 반드시 점수를 얻게 되기까지 최악의 경우 둘 수 있는 수의 개수를 한 줄에 출력한다.