육각 보드

크기가 $N \times N$인 육각 보드가 주어진다. 아래 그림은 $N = 1, 2, 3, 4$인 경우이다.

$i$번째 줄은 $i-1$번째 줄보다 오른쪽으로 반 칸 밀려 있다. 따라서 $(i, j)$칸은 보드 안에 있는 $(i, j-1)$, $(i, j+1)$, $(i-1, j)$, $(i-1, j+1)$, $(i+1, j-1)$, $(i+1, j)$칸과 변을 공유한다.

육각 보드의 일부 칸을 색칠하려고 한다. 변을 공유하는 두 칸은 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 종류 수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$이 주어진다. ($1 \le N \le 50$)

둘째 줄부터 $N$개의 줄에 걸쳐 각 칸의 정보가 주어진다. 각 줄은 길이가 $N$인 문자열이다. 위에서 $i$번째 줄($0 \le i \le N-1$)의 왼쪽에서 $j$번째 문자($0 \le j \le N-1$)가 $(i, j)$칸을 나타내고, '-'이면 색칠하지 않는 칸, 'X'이면 색칠해야 하는 칸이다.

첫째 줄에 필요한 색의 종류 수의 최솟값을 출력한다. 색칠할 칸이 하나도 없으면 $0$을 출력한다.