Vote (Large)

Candidates A and B are the only two people running in an election. Polling already tells us that exactly $N$ voters support A and exactly $M$ voters support B. Since $N$ is greater than $M$, A wins.

Voters arrive at the polling place one at a time. Their order is chosen uniformly at random among all $(N + M)!$ possible orders. After each vote is cast, the poll worker updates the running count and writes down which candidate is ahead so far. If the two counts are equal, no candidate is ahead.

Compute the probability that A stays ahead the whole time, meaning that A is ahead right after every single vote.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $N$ and $M$, the number of voters supporting A and the number supporting B.

Limits

• $1 \le T \le 100$
• $0 \le M < N \le 2000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the probability that A is ahead right after every vote.

Print $y$ with exactly eight digits after the decimal point. If the exact value does not stop at the eighth decimal digit, round it at that digit, and round up when the remainder falls exactly halfway. For example, a probability of $1/512 = 0.001953125$ prints as 0.00195313.

Take $N = 2$ and $M = 1$. There are three voters, two of whom support A. Call those two A1 and A2. The six possible arrival orders are A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. Only the first two keep A ahead right after every vote. With the order A1 B A2, A is ahead after the first vote but tied after the second. So the answer is $2/6 = 0.33333333$.

Take $N = 1$ and $M = 0$. There is a single voter and that voter supports A. Only one order is possible, and A is ahead after that one vote.