몽유병에 걸린 양

Bleatrix Trotter는 단위 정사각형 칸으로 이루어진 무한한 격자인 이차원 들판에 사는 양이다. 그녀의 집은 (0, 0)로 나타내는 단위 칸에 있다. 즉, 모든 좌표는 Bleatrix의 집 칸을 기준으로 주어진다. 하지만 그녀는 몽유병 때문에 현재 좌표 (X, Y)의 단위 칸, 즉 집 칸에서 동쪽으로 X열, 북쪽으로 Y행 떨어진 칸에 있다. Bleatrix를 보호하도록 배정된 두 마리의 양치기 개는 방금 그녀가 사라졌다는 사실을 알아차렸고, 이제 그녀를 집 칸으로 몰아가려 한다.

Bleatrix가 이동하기 전에 매번 두 양치기 개는 원하는 격자 칸 어디로든 이동할 수 있다. 단, 둘이 같은 칸으로 이동할 수 없으며 어느 쪽도 Bleatrix의 현재 칸으로 이동할 수 없다. 양치기 개들이 자리를 잡으면, 몽유병 중인 Bleatrix는 양치기 개가 있는 칸으로 들어가지 않는 방향 중 하나로 무작위 단위 이동을 한다. 즉, 가능한 네 가지 단위 이동(북쪽, 남쪽, 서쪽, 동쪽)의 집합에서 양치기 개가 있는 칸으로 이동하게 되는 선택지를 모두 버린 다음, 남은 이동 중 하나를 균등한 확률로 무작위 선택한다. 그런 다음 양치기 개들은 다시 자리를 정할 수 있으며, 이 과정이 계속된다(Bleatrix와 달리 양치기 개들은 단위 이동을 할 필요가 없다는 점에 유의하라).

Bleatrix가 (0, 0)에 있는 집에 도착하면 몽유병을 멈추고 깨어나 평화롭게 풀을 뜯으며, 그 이후에는 더 이상 이동하지 않는다.

양치기 개들이 Bleatrix가 집에 도착하기까지 이동하는 횟수의 기댓값을 최소화하도록 서로 움직임을 조율한다면, 그 기댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. (테스트 실행당 10초.) 메모리 제한: 1GB. (X, Y) ≠ (0, 0).

테스트 세트 1 (공개)

1 ≤ T ≤ 48. -3 ≤ X ≤ 3. -3 ≤ Y ≤ 3.

테스트 세트 2 (비공개)

1 ≤ T ≤ 100. -500 ≤ X ≤ 500. -500 ≤ Y ≤ 500.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 Bleatrix의 시작 칸 좌표를 나타내는 두 정수 X와 Y가 담긴 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 Bleatrix의 이동 횟수의 기댓값이다. y은 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ의 경쟁 섹션을 참조하라.

X와 Y 중 하나 또는 둘 다의 값이 음수일 수 있다는 점에 유의하라. 예를 들어 X 값이 -1이면 해당 칸이 Bleatrix의 집 칸에서 서쪽으로 한 단위 떨어져 있다는 뜻이다. (마찬가지로 Y 값이 음수이면 해당 칸이 Bleatrix의 집 칸에서 남쪽에 있다는 뜻이다.)

예제 케이스에서 Bleatrix는 처음에 집에서 북쪽으로 한 칸, 서쪽으로 한 칸 떨어진 곳에 있다. 그녀가 처음 이동하기 전에 두 양치기 개는 (-2, 1)과 (-1, 2) 칸에 자리 잡을 수 있다. 그러면 그녀가 어느 방향을 선택하더라도 집에서 한 걸음만 떨어진 곳에 도착하게 된다… 하지만 양치기 개들은 그녀가 다음 이동에서 집으로 갈 것이라고 보장할 수 없다! 나머지 세부 사항은 직접 알아내야 한다.