Breaking Windows (Large)

A room is surrounded by $K$ windows. A window breaks when a stone hits it. $H$ of the windows are reinforced, so each of them survives the first stone and breaks on the second one. The other $K - H$ windows are not reinforced, so each of them breaks on the first stone.

$N$ villains hold a meeting in this room. To mark the occasion, each villain picks one window and throws one stone at it. Each villain picks the target uniformly at random among the $K$ windows, independently of everyone else. A stone thrown at a window that is already broken passes straight through it.

You own the room, so you hire $M$ workers to reinforce the windows before the meeting. Each worker also picks one window uniformly at random among the $K$ windows, independently of everyone else, and reinforces it. Every reinforcement lets that window survive one more stone.

Compute the probability that at least one window is broken after the meeting.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains four integers $K$, $N$, $M$, $H$ separated by spaces.

Constraints

• $1 \le T \le 200$
• $1 \le K \le 200$
• $1 \le N \le 100$
• $1 \le M \le 100$
• $0 \le H \le K$

For each test case, print one line in the form Case #x: y, where $x$ is the case number starting from 1 and $y$ is the probability that at least one window is broken. Round $y$ to eight digits after the decimal point and always print all eight digits.

All three cases in the sample input use a room with three windows.

In the first case the windows stay intact only when the worker reinforces the same window that the stone hits, so the probability of a break is $2/3$.

In the second case, even if a reinforced window survives one stone, no window can survive the other stone, so the probability is $1$.

In the third case the two reinforced windows cannot break. The remaining window breaks only when neither of the two workers reinforces it and the stone hits it, so the probability is $2/3 \times 2/3 \times 1/3 = 4/27$.