떨어지는 다이아몬드

하늘에서 다이아몬드가 떨어지고 있다. 사람들은 다이아몬드가 착지할 수 있는 장소를 사들이고 있는데, 다이아몬드 하나가 그곳에 착지할 경우 그 다이아몬드를 소유하기 위해서다. 당신은 그러한 장소 하나를 제안받았으며, 이것이 좋은 거래인지 알고 싶다.

다이아몬드는 예상했겠지만 다이아몬드 모양이다. 즉, 다이아몬드의 중심이라 부르는 어떤 X, Y에 대해 꼭짓점이 (X-1, Y), (X, Y+1), (X+1, Y), (X, Y-1)인 정사각형이다. 모든 다이아몬드는 항상 X-Y 평면에 있다. X는 수평 방향이고 Y는 수직 방향이다. 지면은 Y=0에 있으며, 양의 Y 좌표는 지면보다 위에 있다.

다이아몬드는 Y축을 따라 하나씩 떨어진다. 즉, 매우 큰 Y에 있는 (0, Y)에서 시작하여 수직으로 내려오다가 지면이나 다른 다이아몬드에 부딪힌다.

다이아몬드가 지면에 부딪히면 중심까지 지면에 묻힐 때까지 떨어진 뒤 움직임을 멈춘다. 이는 사실상 모든 다이아몬드의 중심이 Y=0에 도달하면 낙하하거나 미끄러지는 것을 멈춘다는 뜻이다.

다이아몬드가 다른 다이아몬드와 꼭짓점끼리 부딪히면 회전하지 않은 채 가능한 두 방향 중 하나, 즉 왼쪽 아래나 오른쪽 아래로 미끄러지기 시작할 수 있다. 양쪽 중 어느 쪽도 바로 다이아몬드로 막혀 있지 않다면 같은 확률로 왼쪽이나 오른쪽으로 미끄러진다. 한쪽이 다이아몬드로 막혀 있다면, 떨어지는 다이아몬드는 다른 다이아몬드에 막히거나 지면에 묻힐 때까지 반대쪽으로 미끄러진다. 왼쪽과 오른쪽 경로가 모두 다이아몬드로 막혀 있다면 다이아몬드는 그대로 멈춘다.

그림의 예를 살펴보자. 첫 번째 다이아몬드는 지면에 부딪힌 뒤 중심이 (0, 0)인 상태로 절반이 묻히면 멈춘다. 두 번째 다이아몬드는 같은 확률로 왼쪽이나 오른쪽으로 미끄러질 수 있다. 여기서는 왼쪽으로 갔다. 첫 번째 다이아몬드 옆의 지면에 묻혀 (-2, 0)에서 멈춘다. 세 번째 다이아몬드도 첫 번째 다이아몬드에 부딪힌다. 그러면 무작위로 오른쪽으로 미끄러져 지면에서 멈추거나, 왼쪽으로 미끄러져 이미 놓인 두 다이아몬드의 사이이자 위에서 멈춘다. 이번에도 왼쪽으로 갔으므로 (-1, 1)에서 멈췄다. 네 번째 다이아몬드에는 선택의 여지가 없다. 오른쪽으로 미끄러져 (2, 0)의 지면에서 멈춘다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. -10,000 ≤ X ≤ 10,000. 0 ≤ Y ≤ 10,000. X + Y은 짝수이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 20.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{6}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 세 정수, 즉 떨어지는 다이아몬드의 수 N과 관심 있는 장소의 위치 X, Y가 주어진다. 구매하려는 장소가 반드시 지면 또는 지면 근처에 있을 필요는 없다는 점에 유의하라.

각 테스트 케이스마다 "Case #x: p"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 (1부터 시작), p는 N개의 다이아몬드 중 하나가 떨어져 그 중심이 정확히 (X, Y)에 자리 잡을 확률이다. 답이 정답과의 절대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 부동소수점 수 형식에 관한 설명은 FAQ을 참조하라.