跳蚤宇宙的建设非常成功，吸引了一只粉免前来参观。

跳蚤宇宙由 $n$ 个页面组成，页面编号为 $1$ 到 $n$，其中页面 $1$ 是社区的首页，所有访问者进入社区时都会首先到达页面 $1$。

• 每个页面都会显示自己的编号。
• 每个页面上都有一个红色按钮，点击该按钮会立即返回到页面 $1$。
• 每个页面还包含若干个超链接，指向其他页面或者指向自己。保证每个页面向所有页面（包括自己）各自存在至少一个超链接。

现在，粉免想从页面 $1$ 出发，最终到达页面 $n$。但由于粉免不懂跳蚤语，因此无法识别每个超链接指向的具体页面。

我们将帮助粉免制定行动策略。当粉免到达某个页面时，它会知道该页面的编号，并可以选择以下两个行动之一：

1. 点击红色按钮，立刻返回页面 $1$。
2. 随机选择一个超链接，并点击进入该链接指向的页面（每个超链接被选择的概率相等）。

一旦粉免到达了页面 $n$，任务就完成了，它不会再行动。

由于随机选择一个超链接需要粉免在大脑中生成一个随机数，所以粉免希望尽量避免这个操作。那么请问，在采用最优策略的情况下，粉免从页面 $1$ 到达页面 $n$ 所需的期望 随机选择超链接 的次数最小是多少？（注意 点击红色按钮 并不计入次数）

输入格式

本题的一个测试点包含多个测试数据。

第一行一个正整数 $T$，表示测试数据的组数。对于每组测试数据：

• 第一行一个正整数 $n$，表示跳蚤宇宙的页面总数。
• 接下来 $n$ 行，每行 $n$ 个自然数 $a_{i,j}$，表示页面 $i$ 指向页面 $j$ 的超链接数量。

输出格式

对于每组数据，输出一行，包含一个十进制小数 $\text{ans}$，表示在最优策略下，粉免从页面 $1$ 到页面 $n$ 所需的期望 随机选择超链接 的次数的最小值。

你的答案与参考答案的绝对误差或相对误差不超过 $10^{−6}$ 时被认为是正确的。

样例一

input

3
3
1 1 4
5 1 4
2 3 3
3
9 9 8
2 4 4
3 5 3
5
3 3 5 4 1
4 2 2 4 8
10 10 6 4 2
4 5 6 1 1
10 2 7 6 5

output

1.500000
2.928571
7.392606

explanation

第一组测试样例数据中，最优策略为如果在页面 $1$ 随机选择一个超链接并点开，如果在页面 $2$ 则点击红色按钮回到页面 $1$。

第二组测试样例数据中，最优策略为无论在页面 $1$ 还是页面 $2$，都随机选择一个超链接并点开。

样例二～五

见附件下载。

限制与约定

对于所有数据，保证 $1\leq T\leq100$，$2\leq n\leq200$，$1\leq a_{i,j}\leq100$。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$