백만장자 되기

TV 프로그램 "백만장자가 되고 싶습니까?"에 초대받았다. 규칙은 다음과 같다.

• 게임을 시작하기 전에 진행자가 룰렛을 돌려 한 판을 이길 확률 $P$를 정한다.
• 시작 자금은 $X$달러다.
• 베팅은 $M$번 진행된다. 각 판에서 지금 가진 돈 중 원하는 만큼을 걸 수 있고, 한 푼도 걸지 않아도 되고 전부 걸어도 된다. 거는 금액이 달러나 센트 단위로 딱 맞아떨어져야 하는 것은 아니다.
• 판을 이기면 건 금액만큼 돈이 늘고, 지면 건 금액만큼 돈이 줄어든다.
• $M$번의 베팅이 모두 끝난 뒤 가진 돈이 $1000000 이상이면 그 돈을 그대로 가져간다. 이때 금액은 달러 단위로 내림한다. $1000000 미만이면 아무것도 받지 못한다.

$M$, $P$, $X$가 주어진다. 백만장자가 될 확률이 가장 커지도록 최적으로 플레이할 때, $1000000 이상을 손에 넣을 확률을 구하라.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다.

이어지는 $N$개의 줄에 각각 $M$, $P$, $X$가 공백 하나로 구분되어 주어진다.

• $M$은 베팅 횟수를 나타내는 정수다.
• $P$는 한 판을 이길 확률을 나타내는 실수다.
• $X$는 시작 자금을 나타내는 정수이고 단위는 달러다.

제한:

• $1 \le N \le 100$
• $0 \le P \le 1$, 소수점 아래 자리는 최대 6개다. 소수점이 없는 정수 형태로 주어질 수도 있다.
• $1 \le X \le 1000000$
• $1 \le M \le 5$

각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 백만장자가 될 확률이다.

$y$는 소수점 아래 여섯째 자리까지 반올림해서, 자리가 남으면 0으로 채워 소수점 아래를 항상 여섯 자리로 출력한다. 일곱째 자리가 5이면 올린다. 확률이 정확히 1이면 1.000000, 정확히 0이면 0.000000이다.

$M = 1$, $P = 0.5$, $X = 500000$인 경우 $1000000에 닿는 방법은 한 판에 가진 돈을 전부 거는 것뿐이므로 확률은 $0.5$다.

$M = 3$, $P = 0.75$, $X = 600000$인 경우에는 한 판을 져도 여전히 $1000000에 닿을 수 있게 플레이할 수 있다. 예를 들어 다음처럼 걸면 된다.

• 첫 판에 $600000을 들고 $150000을 건다.
• 첫 판을 졌으면 $450000이 남았고, $100000을 건다.
• 첫 판을 지고 둘째 판을 이겼으면 $550000이 남았고, $450000을 건다.
• 첫 판을 이겼으면 $750000이 남았고, $250000을 건다.
• 첫 판을 이기고 둘째 판을 졌으면 $500000이 남았고, $500000을 건다.