8649: Conquest of Masters Tour

The Hearthstone Masters Tour 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 Conquest, which is also the main match format used in official Hearthstone tournaments. The rule of the format is described as follows.

1. Each player brings a specific number of decks, depending on tournament rules.
2. 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:
1. Any deck that wins a game cannot be played again in the match;
2. Any deck that is defeated may be played again in the subsequent games.
Then a game is played by the two players using the chosen deck.
3. The first player to win with all of their decks wins the match.

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 Ai,jdenotes 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 optimally in each round.

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

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

Then $n$ lines describing the matrix $A$ follow, where the $i(1\le i\le n)$-th line contains nnumbers with at most two decimal places Ai,1,Ai,2,…,Ai,n(0≤Ai,j≤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 ∣a−b∣min(1,∣b∣)≤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