AT_abc448_g [ABC448G] Conquest

高橋君と青木君はカードゲームをします。ゲームは以下のルールで進行します。 - 高橋君がデッキ $ A_1, A_2, \dots, A_N $ を提示する。ここで $ N \geq 3 $ である。 - 青木君がデッキ $ B_1, B_2, B_3 $ を提示する。 - 高橋君は青木君のデッキのうちいずれか $ 1 $ 個を選び BAN する。青木君もまた高橋君のデッキのうちいずれか $ 1 $ 個を選び BAN する。この $ 2 $ つの BAN 操作は **同時に** 行われる。(つまり、一方が他方の選択を知って行動することはできない。) - その後、高橋君と青木君は自身が提示したデッキの中から使用するデッキを **同時に** 宣言する。ただし BAN されたデッキは宣言できない。 - その後、 $ 2 $ 人は宣言したデッキを用いて $ 1 $ 回だけ戦う。戦いの結果、どちらか一方が勝者となる。 整数 $ 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 $ となるように確率を割り当て、その確率に従ってランダムに $ 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} $ 以下である時に正答とみなされる。

### Sample Explanation 1 双方が自身の勝率を最大化するように行動した時の高橋君の勝率は $ 0.5272727 \cdots $ です。 ### Constraints - $ 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 $ 以下 - 入力される値は全て整数