Google Royale

Your team of space explorers visits the planet Theta VIII, gets pulled into the plot of a badly written novel, and ends up stuck in a hotel and casino called the Google Royale. To leave, you have to win enough money at the tables to buy the hotel for $V$ dollars.

You start with $A$ dollars. You play betting rounds until one of two conditions is met. If you finish a betting round with 0 dollars or less, you lose. If you finish a betting round with $V$ dollars or more, you buy the hotel and leave. Otherwise you start a new betting round.

Each betting round consists of one or more coin flips. If you have $X$ dollars when the round starts, you choose an integer $B$ with $1 \le B \le \min(X, M)$ and bet it on the first flip.

With probability $1/2$ you win the flip. The Royale immediately pays you $B$ dollars, you now have $X + B$ dollars, and the round ends.

With probability $1/2$ you lose the flip and owe the Royale $B$ dollars. You may pay what you owe and end the round. If $2B \le M$ you may instead delay the payment and flip again with the bet doubled to $2B$ dollars. If you lose again, you owe $B + 2B = 3B$ dollars. You can keep doubling the bet to $4B$, $8B$ and so on until you win a flip, you choose to stop, or your next bet would exceed $M$. You may keep going even when the bets placed in the current round already add up to more than $X$.

Once the round is over you pay the Royale for every flip you lost, and the Royale pays you for the flip you won, if there was one. Starting from a bet of 1 dollar, losing three flips and then winning one gains you $8 - 4 - 2 - 1 = 1$ dollar. Losing three flips and then stopping loses you $4 + 2 + 1 = 7$ dollars. If the payment leaves you with 0 dollars or less, you are broke and you have lost the game.

An android in your team computes the probability that you win if you follow an optimal strategy. Report that probability, and report the largest first bet you can place while keeping that probability. Remember that no bet may exceed $M$.

A sample play-through

Suppose $A = 5$, $M = 20$, $V = 40$ and you use the following strategy, which is not optimal. This sequence of events is possible.

• Round 1: the first bet may be 1, 2, 3, 4 or 5 dollars. You bet 2 dollars.
  • Step 1 ($B = 2$): you win. You gain 2 dollars and the round ends. You now have 7 dollars.
• Round 2: you bet 5 dollars.
  • Step 1 ($B = 5$): you lose and owe the Royale 5 dollars. Since $5 \times 2 \le 20$ you may flip again with a bet of 10 dollars, but you stop. You lose 5 dollars and the round ends. You now have 2 dollars.
• Round 3: you bet 2 dollars.
  • Step 1 ($B = 2$): you lose and owe 2 dollars. You flip again with a bet of 4 dollars.
  • Step 2 ($B = 4$): you lose and owe 6 dollars in total. That is more than you have, which is allowed. You flip again with a bet of 8 dollars.
  • Step 3 ($B = 8$): you win. You take 8 dollars, pay the $2 + 4 = 6$ dollars you owe, and the round ends. You now have 4 dollars.
• Round 4: you bet 2 dollars.
  • Step 1 ($B = 2$): you lose and owe 2 dollars. You flip again with a bet of 4 dollars.
  • Step 2 ($B = 4$): you lose and owe 6 dollars in total. You flip again with a bet of 8 dollars.
  • Step 3 ($B = 8$): you lose and owe 14 dollars in total. You flip again with a bet of 16 dollars.
  • Step 4 ($B = 16$): you lose and owe 30 dollars in total. Since $2 \times 16 > M$ you cannot flip again and you must pay. You now have $-26$ dollars, so you have lost.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $A$, $M$ and $V$ in that order, separated by single spaces.

Limits

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

For each test case print one line in the form Case #x: y z, where $x$ is the case number starting from 1, $y$ is the probability of winning if you follow an optimal strategy, and $z$ is the largest integer you can place as the first bet of the first betting round while keeping that probability.

Print $y$ rounded to exactly six digits after the decimal point. The exact probability is always farther than $10^{-8}$ from a rounding boundary of the sixth decimal digit, so computing it within an absolute error of $10^{-9}$ rounds to the same value.