대역 배우

당신은 곧 공연될 뮤지컬의 캐스팅 감독이다. 이 뮤지컬에는 N개의 배역이 있으며, 각 배역에 주연 배우 한 명과 대역 배우 한 명, 총 두 명을 캐스팅하려 한다. 주연 배우나 대역 배우는 특정 배역 하나만을 위해 연습하며, 대역 배우의 임무는 주연 배우가 출연할 수 없게 되었을 때 그 배역을 맡는 것이다. 공연이 성공하려면 각 배역의 두 배우 중 적어도 한 명은 출연할 수 있어야 한다.

당신은 뮤지컬에 출연할 배우 2N명을 선발했다. 이들은 모두 상당히 재능이 있으며, 누구든 어떤 배역의 주연 배우나 대역 배우로 캐스팅할 수 있다. 하지만 공연이 개막하기 전에 이들 중 일부가 양자 역학을 다룬 대히트 뮤지컬 Hamiltonian!의 출연진에 합류하기 위해 달아나고 싶은 유혹을 받을 수도 있어 걱정하고 있다. 다행히 당신은 사람의 성격을 매우 잘 판단한다. i번째 배우가 출연할 수 없게 될 확률이 $P_{i}$임을 알고 있다. (이 확률들은 모두 서로 독립이며, 각 배우의 확률은 배정된 배역이나 주연 배우인지 대역 배우인지와 관계없이 동일하다.)

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

최적으로 캐스팅한다면 공연이 성공할 확률은 얼마인가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1GB. 모든 i에 대해 0.0000 ≤ $P_{i}$ ≤ 1.0000.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 4.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 40.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각각은 두 줄로 구성된다. 첫 줄에는 배역의 수를 나타내는 정수 N 하나가 주어진다. 둘째 줄에는 유리수 2N개 $P_{i}$가 주어지며, 이 중 i번째 수는 i번째 배우가 공연에 출연할 수 없게 될 확률을 나타낸다. 이 모든 확률은 정확히 소수점 이하 네 자리의 정밀도로 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 공연이 성공할 확률이다. y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

예제 케이스 #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에서 다른 배우가 출연할 수 없게 될 확률을 뺀 값과 같다.