Grid Aliens

On one planet every alien $a_i$ lives on a point of an $N \times N$ grid. Some aliens like water and some do not. This tendency is called the hydrophilic property, and alien $a_i$ has its own degree $h_i$, a real number with $0 \le h_i \le 1$. An alien that sits away from the border has 4 grid neighbours (up, down, left, right). An alien on a border edge has 3 neighbours, and an alien on a corner has 2.

The friendship of two neighbouring aliens $a_i$ and $a_j$ comes from the two hydrophilic degrees $h_i$ and $h_j$.

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

If two neighbours have the same hydrophilic degree, the friendship is perfect, $\mathrm{friend}(a_i, a_j) = 1$. The critical situation $\mathrm{friend}(a_i, a_j) = 0$ happens when $h_i = 0$ and $h_j = 1$. Friendship is not defined for a pair that is not adjacent, such as $(a, c)$ and $(f, p)$ in Figure 1.

The aliens decided to put up separating fences to reduce the conflicts between groups with different hydrophilic degrees. They first split the grid space into two disjoint regions: the W region for hydrophilic aliens, and the Q region for hydrophobic aliens, who dislike a watery environment and have small hydrophilic degrees. Then they build a closed fence around the Q region to keep conflicting aliens apart. The dotted red curves in Figure 1 are those fences. The aliens $b$, $c$, $f$, $x$, $y$ sit inside a fence and belong to the Q region, while $a$, $d$, $e$, $p$, $q$ sit outside and belong to the W region.

Figure 1. Three dotted red fences separate the Q region from the W region.

There are very many ways to set up the fences. When you build them, it is better to put hydrophilic aliens in the W region and hydrophobic aliens in the Q region. You also want the sum of $\mathrm{friend}(a_i, a_j)$ over the neighbour pairs with $a_i \in W$ and $a_j \in Q$ to be as small as possible. Here $x \in Q$ means that alien $x$ is assigned to the Q region. Every alien belongs to exactly one of Q and W.

The objective function $K$ of this $(W, Q)$ separation problem is the following.

$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)$

The sum in $\mathrm{Cost}_{WQ}$ runs over every pair $(a_i, a_j)$ joined by a grid edge.

Write a program that computes $K$ from the hydrophilic degrees of the aliens on the grid points.

Your program reads from standard input. The first line holds the number of test cases $T$. The first line of each test case holds the grid size $N$ ($3 \le N \le 50$). The next $N$ lines hold the hydrophilic degree $h_{i,j}$ of the alien living at grid position $(i, j)$ as an $N \times N$ matrix. Every $h_{i,j}$ is a real number with $0 \le h_{i,j} \le 1$ and exactly two digits after the decimal point.

Your program writes to standard output. Print exactly one line for each test case. The line holds the real number $K$ with two digits after the decimal point.