The Facebook Whacker Cup is a series of ping-pong tournaments to find the best paddlers on the social network. A tournament consists of \(N\) ping-pong players and \(N - 1\) elimination matches among them. The players are numbered from \(1\) to \(N\) in increasing order of skill.

In each match, two players will be randomly selected from the set of players still in contention (if there are \(x\) players, then all \(x(x-1)/2\) unordered pairs of them are equally likely to be selected). Those players will then play against each other, with the more skilled (higher-numbered) of the two winning with a probability of \(P\). The loser will then be eliminated from the tournament, and will not be involved in any future matches. After \(N - 1\) such matches, there will be exactly one player remaining who will be declared the Whacker Cup champion!

For each player, determine the expected number of matches which will occur while they're still in contention (before they're either eliminated or the tournament concludes). This should include matches which they either directly compete in (including the one in which they lose and get eliminated), or which simply occur before they've been eliminated. Each of your answers must have at most \(10^{-6}\) absolute or relative error to be considered correct.

# Input

Input begins with an integer \(T\), the number of tournaments. For each tournament, there is one line containing the space-separated integer \(N\) and real number \(P\) (given with at most 3 digits after the decimal point).

# Output

For the \(i\)th tournament, output a line containing *"Case #i:"* followed by \(N\) lines, the \(j\)th of which contains a single real number, the expected number of matches which will occur while player \(j\) is still in contention.

# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 8000\)
\(0.5 \le P \le 1.0\)

The sum of \(N\) across all \(T\) tournaments is at most 50,000.

# Explanation of Sample

In the first tournament, player 2 is guaranteed to defeat player 1. Regardless of the result, however, both players will be present for the tournament's single match.

In the second tournament, player 3 is guaranteed to defeat players 1 and 2, while player 2 is guaranteed to defeat player 1. There are three possible, equally-likely sequences of matches (with `A>B` representing a match in which player \(A\) beats player \(B\)):

- `2>1` followed by `3>2`
- `3>1` followed by `3>2`
- `3>2` followed by `3>1`

All players are guaranteed to be in contention during at least the first match. Player 1 has a \(\frac{1}{3}\) chance to also be present for the second match (if the last sequence occurs), player 2's chance is \(\frac{2}{3}\) (if either of the first two sequences occurs), and player 3 is guaranteed to be present for both matches.

In the third tournament, the match results are again deterministic. The first match will feature one of 6 possible player pairs, the second match will feature one of 3 possible pairs of remaining players, and the third match will be between the final pair of players. Overall, there are \(6 * 3 * 1 = 18\) possible scenarios. Across these scenarios, the total counts of hypothetical matches before elimination are 30 for player 1, 35 for player 2, 43 for player 3, and 54 for player 4. Dividing each by 18 yields the expected answer.

In the fourth tournament, matches could go either way with equal probability (skill levels don't matter). There are 6 possible, equally-likely first match outcomes (`1>2`, `2>1`, `1>3`, `3>1`, `2>3`, `3>2`), after which only the eliminated player won't be present for the second match. Therefore, each player has a \(\frac{2}{6}\) chance of being present for one match, and a \(\frac{4}{6}\) chance of being present for both.