AT_abc448_g.[ABC448G] Conquest

高桥和青木进行一场牌组游戏。游戏规则如下。

• 高桥准备牌组 $A_1, A_2, \dots, A_N$，其中 $N \geq 3$。
• 青木准备牌组 $B_1, B_2, B_3$。
• 高桥从青木的牌组中选择一组并将其封禁。青木也从高桥的牌组中选择一组并将其封禁。两人封禁操作同时进行（即任何一方无法根据对方的选择行动）。
• 然后，高桥和青木各自同时声明将使用自己的哪一组牌组，但已被封禁的牌组不能被声明。
• 接下来，两位玩家各用宣布的牌组战斗一次。本局会有一方获胜。

给定整数 $X_{i,j}$（$1 \leq i \leq N, 1 \leq j \leq 3$）。记 $p_{i,j} = \dfrac{X_{i,j}}{10^6}$。$p_{i,j}$ 表示高桥使用 $A_i$ 与青木使用 $B_j$ 时高桥的胜率。两人都预先知道 $p_{i,j}$ 的值。
请计算当双方都采取使自己胜率最大化的行动时，高桥的胜率。

共给出 $T$ 组测试数据，请分别求解。

当双方都想最大化自己的胜率时，每一步每位玩家会为可选项分配概率（概率总和为 $1$），并根据到目前为止公开的信息按概率随机选择一个选项。
每位玩家会选择使“最小可能胜率”最大的策略，即“当对方选择使自己胜率最小的策略时的胜率”。如果有多个满足条件的策略，可以任选其一。
当双方均按上述方针行动时，无论具体策略如何，高桥的胜率均唯一确定。请输出该值。

输入从标准输入读入，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试数据。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每组测试数据包含：

$N$
$X_{1,1}\ X_{1,2}\ X_{1,3}$
$X_{2,1}\ X_{2,2}\ X_{2,3}$
$\vdots$
$X_{N,1}\ X_{N,2}\ X_{N,3}$

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试数据的答案。
对于每组测试数据，当双方都采取最大化自己胜率的策略时，高桥的胜率是多少。若输出的答案与真实值的绝对误差或相对误差不超过 $10^{-6}$，即视为正确。

样例解释 1

双方都最大化自己胜率时，高桥的胜率为 $0.5272727\cdots$。

约束条件

• $1 \leq T \leq 500$
• $3 \leq N \leq 5 \times 10^4$
• $0 \leq X_{i,j} \leq 10^6$
• 所有测试数据中 $N$ 之和不超过 $5 \times 10^4$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译