언더스터디

당신은 새 뮤지컬의 캐스팅 감독이다. 뮤지컬에는 N개의 역할이 있고, 각 역할마다 주연 한 명과 언더스터디 한 명, 두 명의 배우를 캐스팅하려 한다. 주연과 언더스터디는 각각 한 역할만 연습하며, 언더스터디는 주연이 출연할 수 없게 되면 그 역할을 대신 연기한다. 공연이 성공하려면 각 역할마다 두 배우 중 적어도 한 명이 출연할 수 있어야 한다.

뮤지컬에 출연할 2N명의 배우를 선발했다. 이들은 모두 뛰어나서 누구든 어떤 역할의 주연이나 언더스터디로 캐스팅될 수 있다. 하지만 공연이 시작되기 전에 몇몇 배우가 양자역학을 다룬 대형 뮤지컬 Hamiltonian!의 출연진에 합류하겠다며 떠날 수도 있다. 다행히 당신은 사람을 잘 파악한다. i번째 배우가 출연할 수 없게 될 확률은 Pi이다. 이 확률들은 서로 독립이며, 각 배우는 맡은 역할이나 주연, 언더스터디 여부와 관계없이 같은 확률을 가진다.

공연이 성공할 확률이 최대가 되도록 각 역할마다 주연 한 명과 언더스터디 한 명을 배정하려 한다. 즉, 주연과 언더스터디가 모두 출연할 수 없게 되는 역할이 적어도 하나 존재할 확률을 최소화하려 한다.

최적으로 캐스팅했을 때, 공연이 성공할 확률은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 역할의 수 N이 주어진다. 둘째 줄에는 2N개의 유리수 Pi가 주어지며, i번째 수는 i번째 배우가 공연에 출연할 수 없게 될 확률이다. 모든 확률은 소수점 아래 네 자리까지 정확히 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 공연이 성공할 확률이다. y는 정답과의 절대 오차 또는 상대 오차가 10-6 이내이면 정답으로 인정된다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 0.0000 ≤ Pi ≤ 1.0000.

예제 1에서 한 가지 최적의 캐스팅은 0.5000인 배우 둘을 두 역할의 주연으로, 0.2500인 배우 둘을 언더스터디로 배정하는 것이다. 한 역할에서 두 배우가 모두 출연할 수 없게 될 확률은 0.5 × 0.25 = 0.125이다. 따라서 그 역할이 두 배우 중 적어도 한 명에 의해 채워질 확률은 1 - 0.125 = 0.875이다. 두 역할이 모두 채워질 확률, 즉 공연이 성공할 확률은 0.875 × 0.875 = 0.765625이다.

대신 0.5000인 배우 둘을 한 역할에, 0.2500인 배우 둘을 다른 역할에 캐스팅하면 성공 확률은 (1 - 0.50 × 0.50) × (1 - 0.25 × 0.25) = 0.703125로 더 낮다.

예제 2에서는 각 역할에 0.0000인 배우(절대 출연할 수 없게 되지 않는 배우)를 정확히 한 명씩 캐스팅하기만 하면 공연이 반드시 성공한다.

예제 3에서 1.0000인 배우는 항상 출연할 수 없게 되므로, 성공 확률은 다른 배우가 출연할 수 없게 될 확률을 1에서 뺀 값과 같다.