격자 위의 외계인

어느 행성의 외계인 $a_i$는 모두 $N \times N$ 격자점 위에 산다. 물을 좋아하는 외계인도 있고 싫어하는 외계인도 있다. 이 성향을 친수성이라고 부르며, 외계인 $a_i$의 친수성은 $0 \le h_i \le 1$인 실수 $h_i$로 나타낸다. 격자의 경계에 있지 않은 외계인은 상하좌우로 이웃이 4명이다. 경계 변에 있는 외계인은 이웃이 3명, 꼭짓점에 있는 외계인은 이웃이 2명이다.

이웃한 두 외계인 $a_i$와 $a_j$의 친밀도는 두 친수성 $h_i$, $h_j$로 정한다.

$\mathrm{friend}(a_i, a_j) = 1 - |h_i - h_j|$

이웃한 두 외계인의 친수성이 같으면 친밀도는 $\mathrm{friend}(a_i, a_j) = 1$로 완벽하다. $h_i = 0$이고 $h_j = 1$이면 $\mathrm{friend}(a_i, a_j) = 0$인 최악의 상황이 벌어진다. 그림 1의 $(a, c)$나 $(f, p)$처럼 이웃이 아닌 쌍에는 친밀도를 정의하지 않는다.

외계인들은 친수성이 다른 무리 사이의 갈등을 줄이려고 울타리를 세우기로 했다. 그러려면 먼저 격자 공간을 서로 겹치지 않는 두 영역으로 나눠야 한다. 친수성 외계인이 사는 W 영역과, 물기 있는 환경을 싫어해서 친수성 값이 작은 소수성 외계인이 사는 Q 영역이다. 그다음 갈등하는 외계인을 갈라놓도록 Q 영역을 감싸는 닫힌 울타리를 세운다. 그림 1에서 빨간 점선이 그 울타리다. $b$, $c$, $f$, $x$, $y$는 울타리 안쪽인 Q 영역에 있고, $a$, $d$, $e$, $p$, $q$는 바깥쪽인 W 영역에 있다.

그림 1. 빨간 점선 울타리 세 개가 Q 영역을 W 영역과 갈라놓는다.

울타리를 세우는 방법은 아주 많다. 울타리를 세울 때는 친수성 외계인을 W 영역에, 소수성 외계인을 Q 영역에 넣는 편이 좋다. 또 $a_i \in W$이고 $a_j \in Q$인 이웃 쌍의 친밀도 합을 되도록 작게 만들어야 한다. 여기서 $x \in Q$는 외계인 $x$가 Q 영역에 배정되었다는 뜻이다. 모든 외계인은 Q와 W 중 정확히 한 영역에 속한다.

이 $(W, Q)$ 분할 문제의 목적 함수 $K$는 다음과 같다.

$K = \max \left( \mathrm{Cost}_W + \mathrm{Cost}_Q - \mathrm{Cost}_{WQ} \right)$

$\mathrm{Cost}_W = \sum_{a_i \in W} h_i, \qquad \mathrm{Cost}_Q = \sum_{a_j \in Q} (1 - h_j)$

$\mathrm{Cost}_{WQ} = \sum_{a_i \in W,\ a_j \in Q} \mathrm{friend}(a_i, a_j)$

$\mathrm{Cost}_{WQ}$의 합은 격자에서 변으로 이어진 쌍 $(a_i, a_j)$ 전체에 대해 더한 값이다.

격자점 위 외계인의 친수성이 주어질 때 $K$를 구하는 프로그램을 작성하시오.

입력은 표준 입력으로 받는다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 격자의 크기 $N$이 주어진다 ($3 \le N \le 50$). 이어지는 $N$개 줄에는 격자점 $(i, j)$에 사는 외계인의 친수성 $h_{i,j}$가 $N \times N$ 행렬로 주어진다. 모든 $h_{i,j}$는 $0 \le h_{i,j} \le 1$인 실수이고, 소수점 아래가 정확히 두 자리다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 한 줄씩, 실수 $K$를 소수점 아래 두 자리까지 출력한다.