좋은 연립정부

네덜란드의 정치가 큰 혼란에 빠졌습니다. 지난 14년 동안 여섯 번의 연립정부가 구성되었지만, 모두 임기를 채우지 못하고 무너졌습니다. 최근 다시 총선이 치러졌는데, 그 결과를 두고 여러 정치 평론가들이 “구성 불가능”이라고 평할 정도입니다. 이 암울한 상황에서 유일한 희망은, 당신이 연립정부 구성을 조율하는 협상 조정관(informateur)으로 임명되었다는 점입니다. 적절한 연립정부를 찾아내는 것이 당신의 임무입니다.

합리적인 사람인 당신은, 가장 안정적인 연립정부를 이루는 정당들부터 협상을 시작하기로 했습니다. 연립정부란 전체 의석의 과반을 확실히 차지하는 정당들의 집합입니다(즉, 전체 150석 중 최소 76석). 연립정부에 속한 정당 중 단 하나라도 이탈하면 연립정부는 무너지고 새 총선을 치러야 합니다. 어떤 연립정부가 임기를 무사히 마칠 확률은, 그 연립정부에 속한 각 정당이 임기를 마칠 확률들의 곱으로 추정합니다. 각 정당의 확률은 과거 데이터를 바탕으로 산정됩니다.

가장 안정적인 연립정부는 임기를 마칠 확률이 가장 높은 연립정부입니다. 그 확률을 구하세요.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 하나가 주어집니다(최대 100). 이후 각 테스트 케이스는 다음과 같이 주어집니다.

• 한 줄에 정당의 수를 나타내는 정수 $n$ ($1 \le n \le 150$). 이는 최소 한 석 이상을 얻은 정당의 수입니다.
• 이어지는 $n$개의 줄에는 각각 공백으로 구분된 두 정수 $s_i$와 $p_i$가 주어집니다 ($1 \le s_i \le 150$, $1 \le p_i \le 100$). $s_i$는 $i$번째 정당이 얻은 의석 수이고, $p_i$는 그 정당이 임기를 마칠 확률(백분율)입니다.

의석은 모든 정당에 나뉘어 배분되며, 항상 $\sum s_i = 150$입니다.

각 테스트 케이스마다, 가장 안정적인 연립정부가 임기를 마칠 확률(백분율)을 한 줄에 출력합니다. 소수점 아래 정확히 6자리까지 반올림하여 출력하세요.