Falling Diamonds (Large)

Diamonds are falling from the sky. People are buying up the spots where a diamond can land, because whoever owns the spot owns the diamond that lands on it. Someone has offered you one such spot, and you want to know whether the deal is worth taking.

Diamonds are shaped like diamonds: for integers $X$ and $Y$, a diamond is the square with vertices $(X-1, Y)$, $(X, Y+1)$, $(X+1, Y)$ and $(X, Y-1)$, and $(X, Y)$ is called its center. Every diamond lies in the $XY$ plane. $X$ is the horizontal direction and $Y$ is the vertical direction. The ground is at $Y = 0$, and positive $Y$ coordinates are above the ground.

The diamonds fall one at a time along the $Y$ axis. Each one starts at $(0, Y)$ with $Y$ very large and falls straight down until it hits the ground or another diamond.

A diamond that hits the ground sinks until it is buried up to its center, then stops. So a diamond whose center reaches $Y = 0$ stops falling and stops sliding.

A diamond that hits another diamond vertex to vertex can start sliding down, without turning, in one of two directions: down and left, or down and right. If no diamond immediately blocks either side, it slides left or right with equal probability. If a diamond blocks one side, the falling diamond slides to the other side, and it keeps going that way until another diamond blocks it or it becomes buried in the ground. If diamonds block both sides, it stops where it is.

Consider the example in the picture. The first diamond hits the ground and stops half buried, with its center at $(0, 0)$. The second diamond slides left or right with equal probability. Here it went left, and it stopped buried in the ground next to the first diamond, at $(-2, 0)$. The third diamond also hits the first one. Sliding right, it stops buried in the ground; sliding left, it stops between and above the two diamonds already placed. It went left again, so it stopped at $(-1, 1)$. The fourth diamond has no choice. It slides right and stops buried in the ground at $(2, 0)$.

Given that $N$ diamonds fall one after another, compute the probability that one of them ends up with its center exactly at $(X, Y)$.

The first line contains the number of test cases, $T$. Each of the next $T$ lines contains three integers: the number of falling diamonds $N$, and the coordinates $X$, $Y$ of the spot you care about. The spot you are offered does not have to be at or near the ground.

Limits

• $1 \le T \le 100$
• $-10000 \le X \le 10000$
• $0 \le Y \le 10000$
• $X + Y$ is even.
• $1 \le N \le 10^6$

For each test case, print one line in the form Case #x: p, where $x$ is the test case number starting from 1 and $p$ is the probability that one of the $N$ diamonds ends up with its center exactly at $(X, Y)$.

Write $p$ with exactly six digits after the decimal point, rounded at the seventh digit. An empty spot prints as 0.000000 and a spot that is certainly filled prints as 1.000000. The answer is judged as an exact match against this format.