Google Royale (Small)

Your team of explorers is stuck in a hotel casino called the Google Royale. To leave, you have to gamble your way to enough money to buy the hotel for $V$ dollars.

You start with $A$ dollars and you play betting rounds until one of two things happens. If a betting round ends with 0 dollars or less, you lose. If a betting round ends with $V$ dollars or more, you buy the hotel and leave. Otherwise you start another betting round.

A betting round is one or more coin flips. If you hold $X$ dollars when the round starts, you pick an integer $B$ with $1 \le B \le \min(X, M)$ and bet $B$ dollars on the first flip.

Every flip is fair. Winning a flip pays you the amount bet on that flip and ends the round at once. Losing a flip puts you in debt for the amount bet on it. After a loss you may pay what you owe and end the round, or, when twice the last bet is at most $M$, flip again with the bet doubled. The bets inside one round therefore run $B$, $2B$, $4B$, $8B$ and so on, and the doubling stops when you win a flip, when you decide to stop, or when the next bet would exceed $M$. You may keep doubling even when the bets already placed in this round add up to more than $X$.

When the round ends you settle it: you pay for every flip you lost, and the Royale pays you for the single flip you won, if there was one. Say you open with a bet of 1, lose three flips, then win the fourth. You collect 8 and pay 4 + 2 + 1, so you gain 1 dollar. If instead you stop after those three losses, you pay 4 + 2 + 1 and lose 7 dollars. If the settlement leaves you with 0 dollars or less, you are broke and the game is over.

An android in your team computes the probability that you win when you play optimally. Print that probability, together with the largest first bet of the opening round that still attains it. No bet may ever exceed $M$.

A round by round walkthrough

Take $A = 5$, $M = 20$ and $V = 20$, and suppose you play the strategy below, which is not optimal.

• Round 1: the legal first bets are 1 to 5. You bet 2. You win the first flip, gain 2 dollars, and the round ends. You hold 7 dollars.
• Round 2: you bet 5. You lose the first flip and owe 5 dollars. Since 5 * 2 is at most 20 you could flip again with a bet of 10, but you stop. You pay 5 dollars and the round ends. You hold 2 dollars.
• Round 3: you bet 2 and lose, so you owe 2 dollars. You flip again with a bet of 4 and lose, so you owe 6 dollars, which is more than you hold, and that is allowed. You flip again with a bet of 8 and win. You collect 8 dollars, pay the 6 you owe, and the round ends. You hold 4 dollars.
• Round 4: you bet 2 and lose, then 4 and lose, then 8 and lose, then 16 and lose. You owe 2 + 4 + 8 + 16 = 30 dollars. Twice 16 is larger than $M$, so you cannot flip again and you have to settle. You are left with 4 - 30 = -26 dollars, and you have lost.

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

Limits

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

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 under an optimal strategy, and $z$ is the largest first bet that attains that probability. Print $y$ rounded to exactly six digits after the decimal point.