구글 로얄

세타 VIII 행성에 들른 우주 탐사대가 형편없는 소설의 줄거리에 휘말려 구글 로얄이라는 호텔 겸 카지노에 갇혔다. 여기서 빠져나가려면 도박으로 돈을 모아 호텔을 $V$달러에 사들여야 한다.

시작 자금은 $A$달러다. 다음 두 조건 중 하나가 만족될 때까지 베팅 라운드를 반복한다. 어떤 라운드를 마친 뒤 가진 돈이 0달러 이하면 패배한다. 라운드를 마친 뒤 가진 돈이 $V$달러 이상이면 호텔을 사고 떠난다. 둘 다 아니면 새 라운드를 시작한다.

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

확률 $1/2$로 동전 던지기를 이긴다. 카지노가 즉시 $B$달러를 지급하므로 가진 돈은 $X + B$달러가 되고 라운드가 끝난다.

확률 $1/2$로 지고 카지노에 $B$달러를 빚진다. 이때 빚을 갚고 라운드를 끝낼 수 있다. 또는 $2B \le M$이면 지급을 미루고 판돈을 두 배로 올린 $2B$달러로 동전을 한 번 더 던질 수 있다. 또 지면 빚은 $B + 2B = 3B$달러가 된다. 이렇게 $4B$, $8B$처럼 판돈을 계속 두 배로 올릴 수 있으며, 동전 던지기를 이기거나 스스로 멈추거나 다음 판돈이 $M$을 넘게 되면 그만둔다. 이번 라운드에 건 판돈의 합이 $X$를 넘어도 계속할 수 있다.

라운드가 끝나면 진 동전마다 판돈을 지급하고, 이긴 동전이 있으면 그 판돈을 받는다. 판돈 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$): 진다. 카지노에 5달러를 빚진다. $5 \times 2 \le 20$이므로 10달러로 한 번 더 던질 수 있지만 그만둔다. 5달러를 잃고 라운드가 끝난다. 이제 2달러를 가진다.
• 라운드 3: 2달러를 건다.
  • 1단계 ($B = 2$): 진다. 2달러를 빚진다. 4달러로 한 번 더 던진다.
  • 2단계 ($B = 4$): 진다. 빚이 6달러가 된다. 가진 돈보다 많지만 상관없다. 8달러로 한 번 더 던진다.
  • 3단계 ($B = 8$): 이긴다. 8달러를 받고 빚 $2 + 4 = 6$달러를 갚는다. 라운드가 끝나고 이제 4달러를 가진다.
• 라운드 4: 2달러를 건다.
  • 1단계 ($B = 2$): 진다. 빚이 2달러다. 4달러로 한 번 더 던진다.
  • 2단계 ($B = 4$): 진다. 빚이 6달러가 된다. 8달러로 한 번 더 던진다.
  • 3단계 ($B = 8$): 진다. 빚이 14달러가 된다. 16달러로 한 번 더 던진다.
  • 4단계 ($B = 16$): 진다. 빚이 30달러가 된다. $2 \times 16 > M$이므로 더 던질 수 없고 빚을 갚아야 한다. 이제 $-26$달러이므로 패배했다.

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

제한

• $1 \le T \le 100$
• $1 \le M \le 10^{16}$
• $1 \le A < V \le 10^{16}$

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 케이스 번호, $y$는 최적 전략을 따를 때의 승리 확률, $z$는 그 확률을 그대로 유지하면서 첫 라운드의 첫 판돈으로 걸 수 있는 가장 큰 정수다.

$y$는 소수점 아래 여섯째 자리에서 반올림해 소수점 아래를 정확히 여섯 자리로 출력한다. 정확한 확률과 여섯째 자리 반올림 경계값의 차이는 항상 $10^{-8}$보다 크므로, 절대 오차 $10^{-9}$ 이내로 계산하면 같은 값으로 반올림된다.