Good Coalition

Dutch politics is in turmoil. Over the past fourteen years there have been six coalition governments, and every one of them collapsed before finishing its term. Elections have just been held again, and the result has been called “impossible” by several political commentators. The one bright spot in this bleak situation is that you have been appointed as the informateur — the person whose job is to find a workable coalition.

Being the rational person you are, you decide to open negotiations with the parties that form the most stable coalition. A coalition is any set of parties that together hold a strict majority of the seats (at least 76 of the 150 seats). A coalition collapses, forcing new elections, the moment any single party leaves it. The probability that a coalition finishes its term is estimated as the product of the probabilities that each of its member parties finishes its term; those per-party probabilities come from historical data.

The most stable coalition is the one with the highest probability of finishing its term. Find that probability.

The first line contains one positive integer: the number of test cases (at most 100). Each test case is given as follows.

• One line with an integer $n$ ($1 \le n \le 150$), the number of parties that won at least one seat.
• $n$ lines, each with two space-separated integers $s_i$ and $p_i$ ($1 \le s_i \le 150$ and $1 \le p_i \le 100$): the number of seats won by party $i$ and the probability (as a percentage) that party $i$ finishes its term.

The seats are shared among all parties so that $\sum s_i = 150$.

For each test case, print one line with the probability (as a percentage) that the most stable coalition finishes its term, rounded to and printed with exactly 6 digits after the decimal point.