有 $n$ 个变量，$x_1, x_2, \dots, x_n$。你需要保证 $x_i \geq 0, \sum_{i=1}^n x_i = 1$。

并且最大化 $\sum_{i=1}^n \sum_{j=i+1}^n w_{i, j} x_i x_j$。

输入格式

多组测试数据，第一行一个数 $T$ 表示数据组数。

对于每组数据：

第一行一个整数 $n$。

接下来 $n$ 行，每行 $n$ 个整数 $w_{i,j}$。保证 $w_{i, j} = w_{j, i}$ 且 $w_{i, i} = 0$。

输出格式

对于每组数据，一个实数，表示答案。相对精度或者绝对精度误差 $10^{-10}$ 即可。

样例输入1

1
3
0 2 1
2 0 2
1 2 0

样例输出1

0.5714285714

样例输入输出2

见下发文件。

数据范围

$10\%$, $n \leq 3$。

$30\%$, $n \leq 5$。

$60\%$, $n \leq 7$。

$100\%$, $2\leq n \leq 10, 1\leq T \leq 20, 0\leq w_{i,j} \leq 1000$。