백만장자

당신은 인기 있는 TV 프로그램 "백만장자가 되고 싶습니까?"에 초대받았다. 물론 되고 싶을 것이다!

프로그램의 규칙은 간단하다.

• 게임이 시작되기 전에 진행자가 행운의 바퀴를 돌려 각 내기에서 이길 확률 P를 결정한다.

• 당신은 일정 금액인 X달러를 가지고 시작한다.

• 내기는 M개의 라운드로 이루어진다. 각 라운드에서 현재 가진 돈의 일부를 얼마든지 걸 수 있으며, 전혀 걸지 않거나 전부 걸 수도 있다. 거는 금액은 달러나 센트의 정수 단위로 제한되지 않는다. 내기에서 이기면 가진 돈의 총액이 건 금액만큼 증가한다. 그렇지 않으면 가진 돈이 건 금액만큼 감소한다.

• 모든 내기 라운드가 끝난 뒤, $1000000 이상을 모은 경우에만 딴 돈을 가질 수 있다(이때 금액은 달러 정수 단위로 내림한다). 그렇지 않으면 아무것도 받지 못한다.

M, P, X가 주어질 때, 최적으로 플레이하는 경우(즉, 백만장자가 될 가능성을 최대화하도록 플레이하는 경우) 적어도 $1000000을 얻을 확률을 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ N ≤ 100 0 ≤ P ≤ 1.0, 소수점 뒤에는 최대 6개의 숫자가 있다. 1 ≤ X ≤ 1000000

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

1 ≤ M ≤ 5

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

1 ≤ M ≤ 15

입력의 첫 줄에는 테스트 케이스의 수 N이 주어진다.

이어지는 N개의 각 줄은 "M P X" 형식이며, 각 항목의 의미는 다음과 같다.

• M은 내기 라운드의 수를 나타내는 정수이다.

• P는 각 라운드에서 이길 확률을 나타내는 실수이다.

• X는 처음에 가진 달러의 수를 나타내는 정수이다.

각 테스트 케이스마다 "Case #X: Y"을 한 줄에 출력한다. 여기서 각 항목의 의미는 다음과 같다.

• X는 1부터 시작하는 테스트 케이스 번호이다.

• Y는 백만장자가 될 확률이며, 0과 1 사이의 값이다.

상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 인정된다.

첫 번째 경우에는 $1000000에 도달하는 유일한 방법이 하나뿐인 라운드에서 가진 돈을 전부 거는 것이다.

두 번째 경우에는 내기에서 지더라도 여전히 $1000000에 도달할 수 있도록 플레이할 수 있다. 다음은 그 방법 중 하나이다.

• 첫 번째 라운드에서 $600000을 가지고 있다. $150000을 건다.

• 첫 번째 라운드에서 지면 $450000이 남는다. $100000을 건다.

• 첫 번째 라운드에서 지고 두 번째 라운드에서 이기면 $550000이 남는다. $450000을 건다.

• 첫 번째 라운드에서 이기면 $750000이 남는다. $250000을 건다.

• 첫 번째 라운드에서 이기고 두 번째 라운드에서 지면 $500000이 남는다. $500000을 건다.