Google Royale

행성 Theta VIII을 방문하던 중, 당신의 우주 탐사대는 형편없이 쓰인 책의 줄거리에 휘말려 Google Royale이라는 호텔 겸 카지노에서 강제로 참여하게 된다. Royale에서 탈출하려면 도박으로 호텔을 V달러에 사서 떠날 수 있을 만큼 충분한 돈을 벌어야 한다.

당신은 A달러로 시작하며, 두 조건 중 하나가 충족될 때까지 베팅 라운드에 참여한다. 어느 베팅 라운드든 마쳤을 때 가진 돈이 ≤ 0달러이면 패배하고, 베팅 라운드를 마쳤을 때 가진 돈이 ≥ V달러이면 호텔을 사서 떠난다. 어느 쪽도 아니라면 새로운 베팅 라운드를 계속 시작한다.

각 베팅 라운드는 한 번 이상의 동전 던지기로 구성된다. 라운드를 시작할 때 X달러를 가지고 있다면, 첫 번째 동전 던지기에 걸 금액으로 1 이상 min(X, M) 이하인 임의의 정수 B을 선택할 수 있다.

50%의 확률로 동전 던지기에서 이기며, Royale은 즉시 B달러를 지급한다. 이제 가진 돈은 X + B달러가 되고 베팅 라운드는 끝난다.

50%의 확률로 동전 던지기에서 지며 Royale에 B달러를 빚진다. 이제 빚진 B달러를 지불하고 라운드를 끝낼 수 있다. 또는 2B ≤ M이면 지불을 미루는 대신 베팅액을 두 배로 늘린 2B달러로 두 번째 동전 던지기를 할 수 있다. 또 지면 Royale에 B+2B=3B달러를 빚진다. 이런 식으로 베팅액을 4B, 8B 등으로 계속 두 배씩 늘릴 수 있으며, 동전 던지기에서 이기거나, 중단하기로 선택하거나, 다음 베팅액이 M을 초과할 때까지 계속할 수 있다. 현재 베팅 라운드에서 모든 베팅액의 합이 X을 초과하더라도 계속할 수 있다.

라운드가 끝나면 진 동전 던지기마다 Royale에 돈을 지불해야 하며, 동전 던지기에서 이겼다면 Royale이 그에 대한 돈을 지급한다. 예를 들어 1달러를 베팅하는 것으로 시작하여 동전 던지기에서 세 번 진 뒤 한 번 이기면, $8 -$4 - $2 -$1 = $1만큼 얻게 된다. 동전 던지기에서 세 번 진 뒤 중단했다면 $4 + $2 +$1 = $7만큼 잃는다. 지불한 뒤 남은 돈이 $0 이하라면 파산하며, 방금 게임에서 패배한 것이다.

다행히 당신은 안드로이드를 데려왔고, 그는 최적 전략을 따를 때 이길 확률을 계산할 수 있다. 그 확률은 얼마이며, 그 확률을 얻으면서 할 수 있는 첫 베팅의 가능한 최대 금액은 얼마인가? M보다 많이 베팅할 수 없다는 점을 기억하라!

예제

다음과 같은 (최적이 아닌) 전략을 사용하기로 했다고 가정하자. 당신은 A=5달러를 가지고 있으며, M=20이고 V=40이다. 다음과 같은 사건의 흐름이 가능하다:

• 라운드 1: 처음에는 1, 2, 3, 4, 5달러 중 하나를 베팅할 수 있다. 당신은 2달러를 베팅하여 베팅 라운드를 시작하기로 한다.

• 단계 1 (B=$2): 첫 번째 동전 던지기에서 이긴다. 2달러를 얻고 베팅 라운드가 끝난다. 이제 7달러를 가지고 있다.

• 라운드 2: 5달러를 베팅하여 베팅 라운드를 시작한다.

• 단계 1 (B=$5): 첫 번째 동전 던지기에서 진다. 이제 Royale에 5달러를 빚진다. 5*2 ≤ 20이므로, 5*2=10달러를 베팅하여 동전을 한 번 더 던질 수 있다. 그렇게 하지 않기로 한다. 5달러를 잃고 베팅 라운드가 끝난다. 이제 2달러를 가지고 있다.

• 라운드 3: 2달러를 베팅하여 베팅 라운드를 시작한다.

• 단계 1 (B=$2): 진다. 이제 Royale에 2달러를 빚진다. 4달러를 베팅하여 동전을 한 번 더 던지기로 한다.

• 단계 2 (B=$4): 진다. 이제 Royale에 총 6달러를 빚진다. 이는 가진 돈보다 많지만 괜찮다. 8달러를 베팅하여 동전을 한 번 더 던지기로 한다.

• 단계 3 (B=$8): 이긴다. 8달러를 받고, 빚진 2+4=6달러를 지불하면 베팅 라운드가 끝난다. 이제 4달러를 가지고 있다.

• 라운드 4: 2달러를 베팅하여 베팅 라운드를 시작한다.

• 단계 1 (B=$2): 진다. 이제 Royale에 2달러를 빚진다. 4달러를 베팅하여 동전을 한 번 더 던지기로 한다.

• 단계 2 (B=$4): 진다. 이제 Royale에 총 6달러를 빚진다. 8달러를 베팅하여 동전을 한 번 더 던지기로 한다.

• 단계 3 (B=$8): 진다. 이제 Royale에 총 14달러를 빚진다. 16달러를 베팅하여 동전을 한 번 더 던지기로 한다.

• 단계 4 (B=$16): 진다. 이제 Royale에 총 30달러를 빚진다. 2*16>M이므로 동전을 한 번 더 던질 수 없으며, 빚진 금액을 지불해야 한다. 이제 -26달러를 가지고 있으며, 패배했다.

제한

1 ≤ T ≤ 100. 메모리 제한: 1GB.

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

1 ≤ M ≤ 20. 1 ≤ A < V ≤ 20. 시간 제한: 30초.

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

1 ≤ M ≤ $10^{16}$. 1 ≤ A < V ≤ $10^{16}$. 시간 제한: 60초.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 하나의 공백으로 구분된 세 정수 A, M, V가 이 순서대로 주어진다.

각 테스트 케이스마다 "Case #x: y z"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 최적 전략을 따를 때 이길 확률이며, z는 승리 확률을 낮추지 않으면서 할 수 있는 첫 베팅의 최대 금액이다. y의 절대 오차 또는 상대 오차는 10^{-6} 이내여야 한다.