Google Royale (Small)

탐사대가 Google Royale이라는 호텔 카지노에 갇혔다. 이곳을 떠나려면 도박으로 돈을 모아 호텔을 $V$달러에 사야 한다.

$A$달러를 들고 시작해서, 다음 두 조건 중 하나를 만족할 때까지 베팅 라운드를 반복한다. 어떤 라운드가 끝났을 때 가진 돈이 0달러 이하이면 진다. 라운드가 끝났을 때 가진 돈이 $V$달러 이상이면 호텔을 사서 떠난다. 둘 다 아니면 새 라운드를 시작한다.

한 라운드는 동전 던지기 한 번 이상으로 이루어진다. 라운드를 시작할 때 가진 돈이 $X$달러이면 $1 \le B \le \min(X, M)$인 정수 $B$를 골라 첫 동전에 $B$달러를 건다.

동전은 앞뒤가 각각 1/2 확률이다. 동전을 맞히면 그 판에 건 금액을 받고 라운드가 곧바로 끝난다. 틀리면 그 금액만큼 빚을 진다. 틀린 뒤에는 빚을 갚고 라운드를 끝내도 되고, 직전 베팅액의 두 배가 $M$ 이하이면 베팅액을 두 배로 올려 한 번 더 던져도 된다. 그래서 한 라운드 안의 베팅액은 $B$, $2B$, $4B$, $8B$처럼 이어지고, 동전을 맞히거나 그만두기로 하거나 다음 베팅액이 $M$을 넘으면 거기서 끝난다. 이번 라운드에서 이미 건 금액의 합이 $X$를 넘어도 계속 두 배로 올릴 수 있다.

라운드가 끝나면 정산한다. 틀린 판마다 건 금액을 내고, 맞힌 판이 있으면 그 금액을 받는다. 1달러로 시작해 세 번 틀리고 네 번째에 맞혔다면 8달러를 받고 4 + 2 + 1달러를 내므로 1달러를 번다. 세 번 틀린 뒤 그만뒀다면 4 + 2 + 1달러를 잃는다. 정산하고 남은 돈이 0달러 이하이면 파산이고 그대로 게임에서 진다.

일행 중 안드로이드가 최적 전략을 따를 때의 승리 확률을 계산해 준다. 그 확률과, 그 확률을 그대로 유지하면서 첫 라운드의 첫 판에 걸 수 있는 가장 큰 금액을 구하여라. 어떤 베팅도 $M$을 넘을 수 없다.

라운드별 진행 예시

$A = 5$, $M = 20$, $V = 20$이고 아래처럼 최적이 아닌 전략을 쓴다고 하자.

• 라운드 1: 첫 베팅으로 1부터 5까지 고를 수 있다. 2달러를 건다. 첫 동전을 맞혀 2달러를 얻고 라운드가 끝난다. 이제 7달러가 있다.
• 라운드 2: 5달러를 건다. 첫 동전을 틀려 5달러를 빚진다. 5 * 2가 20 이하이므로 10달러로 한 번 더 던질 수 있지만 그만둔다. 5달러를 내고 라운드가 끝난다. 이제 2달러가 있다.
• 라운드 3: 2달러를 걸어 틀리고 2달러를 빚진다. 4달러로 한 번 더 던져 또 틀려서 빚이 6달러가 된다. 가진 돈보다 많지만 상관없다. 8달러로 한 번 더 던져 맞힌다. 8달러를 받고 빚 6달러를 갚으면 라운드가 끝난다. 이제 4달러가 있다.
• 라운드 4: 2, 4, 8, 16달러를 차례로 걸어 네 번 모두 틀린다. 빚은 2 + 4 + 8 + 16 = 30달러다. 16의 두 배는 $M$보다 크므로 더 던질 수 없고 정산해야 한다. 4 - 30 = -26달러가 남아 게임에서 졌다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개 줄에는 각각 세 정수 $A$, $M$, $V$가 공백 하나로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le M \le 20$
• $1 \le A < V \le 20$

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 케이스 번호, $y$는 최적 전략을 따를 때의 승리 확률, $z$는 그 확률을 유지하면서 첫 판에 걸 수 있는 가장 큰 금액이다. $y$는 소수점 아래 일곱째 자리에서 반올림해 여섯 자리로 출력한다.