떨어지는 다이아몬드 (큰 입력)

하늘에서 다이아몬드가 떨어진다. 다이아몬드가 떨어질 수 있는 자리를 사람들이 사들이고 있다. 그 자리에 다이아몬드가 하나라도 떨어지면 그것을 갖게 되기 때문이다. 나도 그런 자리 하나를 사라는 제안을 받았고, 이 거래가 이득인지 알고 싶다.

다이아몬드는 이름 그대로 마름모 모양이다. 어떤 정수 $X$, $Y$에 대해 꼭짓점이 $(X-1, Y)$, $(X, Y+1)$, $(X+1, Y)$, $(X, Y-1)$인 정사각형이고, $(X, Y)$를 그 다이아몬드의 중심이라고 한다. 모든 다이아몬드는 $XY$ 평면 위에 있다. $X$는 수평 방향, $Y$는 수직 방향이다. 땅은 $Y = 0$이고, $Y$ 좌표가 양수인 곳은 땅 위다.

다이아몬드는 $Y$축을 따라 하나씩 떨어진다. 즉 $Y$가 아주 큰 위치 $(0, Y)$에서 출발해 수직으로 내려오다가 땅이나 다른 다이아몬드에 부딪힌다.

땅에 부딪힌 다이아몬드는 중심까지 땅에 박힐 때까지 내려간 다음 멈춘다. 즉 중심이 $Y = 0$에 닿은 다이아몬드는 더 이상 떨어지지도, 미끄러지지도 않는다.

다른 다이아몬드와 꼭짓점끼리 부딪힌 다이아몬드는 방향을 바꾸지 않고 왼쪽 아래나 오른쪽 아래, 두 방향 중 하나로 미끄러져 내려갈 수 있다. 양쪽 어느 쪽에도 바로 막고 있는 다이아몬드가 없으면 왼쪽과 오른쪽으로 같은 확률로 미끄러진다. 한쪽이 막혀 있으면 반대쪽으로 미끄러지고, 다른 다이아몬드에 막히거나 땅에 박힐 때까지 그 방향으로 계속 내려간다. 양쪽 모두 막혀 있으면 그 자리에서 멈춘다.

그림의 예를 보자. 첫 번째 다이아몬드는 땅에 부딪혀 절반쯤 박힌 채 중심이 $(0, 0)$인 자리에서 멈춘다. 두 번째 다이아몬드는 왼쪽과 오른쪽으로 같은 확률로 미끄러진다. 그림에서는 왼쪽으로 갔고, 첫 번째 다이아몬드 옆 $(-2, 0)$에 박혀 멈췄다. 세 번째 다이아몬드도 첫 번째 다이아몬드에 부딪힌다. 오른쪽으로 미끄러지면 땅에 박혀 멈추고, 왼쪽으로 미끄러지면 이미 놓인 두 다이아몬드 사이 위쪽에서 멈춘다. 그림에서는 다시 왼쪽으로 가서 $(-1, 1)$에 멈췄다. 네 번째 다이아몬드에는 선택의 여지가 없다. 오른쪽으로 미끄러져 $(2, 0)$에서 땅에 박힌다.

다이아몬드 $N$개가 차례로 떨어졌을 때, 그중 하나의 중심이 정확히 $(X, Y)$에 놓일 확률을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 정수 세 개가 주어진다. 떨어지는 다이아몬드의 개수 $N$, 그리고 관심 있는 자리의 좌표 $X$, $Y$이다. 사려는 자리가 땅이나 땅 근처일 필요는 없다.

제한

• $1 \le T \le 100$
• $-10000 \le X \le 10000$
• $0 \le Y \le 10000$
• $X + Y$는 짝수다.
• $1 \le N \le 10^6$

각 테스트 케이스마다 한 줄에 Case #x: p 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $p$는 떨어진 다이아몬드 $N$개 중 하나의 중심이 정확히 $(X, Y)$에 놓일 확률이다.

$p$는 소수점 아래 여섯 자리까지 쓰고, 일곱째 자리에서 반올림한다. 자리가 비어 있으면 0.000000, 확실히 채워지면 1.000000이 된다. 채점은 이 형식과 정확히 일치하는지로 한다.