Conquest of Masters Tour

The <i>Hearthstone Masters Tour</i> is a tournament for the famous card-collecting game Hearthstone, consisting of live and online events hosted every year in which Masters Qualifiers winners, Hearthstone Grandmasters, and other invitees compete for massive prize money.

In the Hearthstone Masters Tour, players are paired to play against each other in the format of <i>Conquest</i>, which is also the main match format used in official Hearthstone tournaments. The rule of the format is described as follows.

<ol>
<li> Each player brings a specific number of decks, depending on tournament rules. </li>
<li> To begin playing a round, each player chooses one of their decks to battle the opponent with, with the deck choice hidden from the opponent. The decks chosen by each player must satisfy the following rules: </li>
<ol>
<li> Any deck that wins a game cannot be played again in the match; </li>
<li> Any deck that is defeated may be played again in the subsequent games. </li>
</ol>
Then a game is played by the two players using the chosen deck.
<li> The first player to win with all of their decks wins the match. </li>
</ol>

Now you are playing a match in some Hearthstone Masters Tour where each player brings $n$ decks and the decks are determined. You are given an $n$ by $n$ matrix $A$ where $A_{i,j}$ denotes the probability of winning a game if you choose the $i$-th deck and your opponent chooses the $j$-th deck.


You want to know, what is the maximum probability you will win the match, supposing your opponent knows your strategy and chooses the deck <strong>optimally</strong> in each round.

The first line contains an integer $T$, denoting the number of test cases. $(1\leq T\leq 5)$.

For each test case, the first line contains an integer $n(1\leq n\leq 8)$, denoting the number of decks each player brings.

Then $n$ lines describing the matrix $A$ follow, where the $i(1\leq i\leq n)$-th line contains $n$ numbers with at most two decimal places $A_{i,1},A_{i,2},\dots,A_{i,n}( 0\leq A_{i,j} \leq 1)$.

For each test case, output a number in one line, denoting the answer. Your answer is considered correct, if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\vert a-b\vert \min(1,\vert b\vert)\leq 10^{-6}$.

3
1
0.50
3
1.00 1.00 1.00
1.00 1.00 1.00
0.00 0.00 0.00
3
1.00 0.00 0.00
0.00 1.00 0.00
0.00 0.00 1.00

0.5000000000
0.0000000000
0.1666666667

2022“杭电杯”中国大学生算法设计超级联赛（9）