Fat brother and Maze are playing a kind of special (hentai) rock-paper-scissors game with N friends in the house (so totally N+2 people). At each turn, each player plays Rock, Paper or Scissors by their hands at the same time. Rock defeats scissors, scissors defeats paper and paper defeats rock. If everyone play the same item or all the three items (rock, paper and scissors) show up, the game is tied. Otherwise, the one who lose in this turn will leave the house and play a MORE special (hentai) game outside. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.) And the rest of them will go into the next turn. The game ends until there is only one guy left in the house.
As Fat brother loves Maze very much, he doesn’t want Maze left the house. (pure evil guy, you know why) So before this special (hentai) game, he investigate all the other people (include Maze) and knows the probability they will play rock, paper, scissors during the game. So he decides to try him best to let Maze win. You can assume that this probability would never change. Now your task is to calculate the probability that Maze can win while Fat brother choose his best strategy and ALL other people play randomly. Note that Fat brother wants Maze win, not himself.
The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow, each an integer N described above.
Then a line with three decimal numbers describe the probability that Maze will play rock, paper, scissors during the game
Then N lines follow, the ith line contains three decimal numbers which descript the probability that the ith friend will play rock, paper, and scissors during the game.
1 <= T <= 100, 1 <= N <= 15.
In 99% of the test cases, 1 <= N <= 10.
Each probability is larger than 0.1 with at most 2 digits after decimal point.
For each case, output the probability that Maze can win while Fat brother choose his best strategy and ALL other people play randomly.
Your answer will be accepted if your absolute error for each number is no more than 10-4.
2 0 0.2 0.2 0.6 1 0.2 0.2 0.6 0.3 0.3 0.4
0.750000000000 0.507352941176