방황하는 로봇

Jemma는 로봇 공학 대회에 참가하고 있다. 오늘의 과제는 경기장에 있는 구멍을 피해 이동할 수 있는 로봇을 만드는 것이다.

경기장은 W개의 열(왼쪽에서 오른쪽으로 1부터 W까지 번호가 매겨짐)과 H개의 행(위쪽에서 아래쪽으로 1부터 H까지 번호가 매겨짐)으로 이루어진 정사각형 격자이다. x번째 열과 y번째 행에 있는 칸을 (x, y)로 나타낸다. 로봇은 왼쪽 위 칸 (1,1)에서 시작하며 오른쪽 아래 칸 (W, H)까지 이동해야 한다.

직사각형 모양의 부분 격자가 격자에서 잘려 나갔다. 더 구체적으로, 왼쪽 위 칸이 (L, U)이고 오른쪽 아래 칸이 (R, D)인 직사각형에 포함되는 모든 칸이 제거되었다.

Jemma는 로봇을 프로그래밍할 시간이 많지 않았으므로 로봇은 매우 단순한 알고리즘을 따른다.

• 로봇이 가장 오른쪽 열에 있으면 항상 바로 아래 칸으로 이동한다. 그렇지 않고,

• 로봇이 가장 아래쪽 행에 있으면 항상 바로 오른쪽 칸으로 이동한다. 그렇지 않으면,

• 로봇은 바로 오른쪽 칸 또는 바로 아래 칸 중 하나를 같은 확률로 무작위 선택하여 이동한다.

로봇이 구멍에 빠지지 않고 (W, H) 칸에 도착하면 Jemma는 과제를 통과한다. Jemma가 과제를 통과할 확률은 얼마인가?

제한

시간 제한: 15초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ U ≤ D ≤ H. 1 ≤ L ≤ R ≤ W. 왼쪽 위 칸과 오른쪽 아래 칸은 모두 제거되지 않는다.

테스트 세트 1

1 ≤ W ≤ 300. 1 ≤ H ≤ 300.

테스트 세트 2

1 ≤ W ≤ $10^{5}$. 1 ≤ H ≤ $10^{5}$.

입력의 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 W, H, L, U, R, D가 주어지는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 Jemma가 과제를 통과할 확률을 나타내는 0 이상 1 이하의 실수이다.

y이 정답과의 절대 오차 또는 상대 오차가 10^{-5} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고한다.