ARAM (Small)

League of Legends has a mode called "ARAM", short for "All Random, All Mid". This problem borrows the idea, and you do not need to have played the game to follow it.

Every time you start a game you are assigned one of $N$ champions uniformly at random. You win more often with some champions than with others, so an unlucky assignment leaves you wishing for a different one. The game has a reroll function for exactly that.

Rerolling works like a kind of money. Before your first game you start with $R$ RD (reroll dollars). You can reroll only while you hold at least 1 RD, and each reroll costs 1 RD. After every game you gain $1/G$ RD, where $G$ is an integer, but your balance never rises above $R$: if you hold $R$ RD and play a game, you still hold $R$ RD when that game ends.

If you hold at least 1 RD and choose to reroll, you spend 1 RD and are assigned one of the $N$ champions uniformly at random again. The champion you already had can come up again. If you dislike the new champion and still hold at least 1 RD, you reroll again. You can keep rerolling as long as you hold at least 1 RD.

For example, take $R = 2$ and $G = 2$. If you use one reroll in your first game, your balance is 1.5 RD when that game ends. Play another game without rerolling and the balance becomes 2.0 RD. Play a third game without rerolling and the balance is still 2.0 RD, because it never rises above $R = 2$. Use two rerolls in the next game and the balance is 0.5 RD when that game ends.

You are given the list of champions and the probability that you win a game played with each of them. If you play $10^{100}$ games and choose your strategy optimally, what fraction of the games do you expect to win?

The first line contains the number of test cases $T$. Each test case starts with a line holding three space separated integers $N$, $R$ and $G$. The next line holds $N$ space separated real numbers $P_1, P_2, \ldots, P_N$, where $P_i$ is the probability that you win a game played with champion $i$.

$1 \le T \le 100$, $1 \le N \le 1000$, $1 \le R \le 4$, $1 \le G \le 4$. Every $P_i$ is written with exactly four digits after the decimal point and satisfies $0 \le P_i \le 1$.

For each test case print one line of the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the fraction of the $10^{100}$ games you win under an optimal strategy. Round $y$ to nine digits after the decimal point and print all nine of them.

League of Legends is a trademark of Riot Games. Riot Games has no involvement with this problem.