투표

A와 B는 어떤 선거에서 경쟁하는 유일한 두 후보이다. 여론 조사에 따르면 정확히 N명의 유권자가 A를 지지하고, 정확히 M명의 유권자가 B를 지지한다. 또한 N이 M보다 크다는 것을 알고 있으므로 A가 승리한다.

유권자들은 가능한 모든 (N + M)!가지 순서 중 균등한 확률로 무작위 선택된 순서에 따라 한 번에 한 명씩 투표소에 도착한다. 각 유권자가 투표한 뒤, 투표소 직원은 결과를 갱신하고 그 시점까지 어느 후보가 앞서고 있는지 기록한다. 앞서는 후보가 없을 수도 있다. (득표수가 같으면 어느 후보도 앞서고 있는 것으로 간주하지 않는다.)

A가 내내 선두를 유지할 확률, 즉 모든 투표가 끝날 때마다 A가 항상 앞서 있을 확률은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB.

소규모 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ M < N ≤ 10.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ M < N ≤ 2000.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나가 포함된 한 줄로 시작한다. 각 테스트 케이스는 두 정수 N과 M이 있는 한 줄로 이루어지며, 각각 A와 B를 지지하는 유권자의 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), y은 모든 투표가 끝날 때마다 A가 항상 앞서 있을 확률이다.

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

예제 케이스 #1에는 3명의 유권자가 있다. 그중 두 명은 A를 지지하며, 이들을 A1와 A2라고 부르기로 한다. 나머지 한 명은 B를 지지한다. 이들이 투표하러 오는 순서는 여섯 가지가 가능하다: A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. 이 순서들 중 처음 두 순서만 모든 투표가 끝날 때마다 후보 A가 앞서 있음을 보장한다. (예를 들어 순서가 A1 B A2이면, 후보 A는 첫 번째 투표 후에는 앞서 있지만 두 번째 투표 후에는 동률이다.) 따라서 답은 2/6 = 0.333333...이다.

예제 케이스 #2에는 유권자가 1명뿐이며, 그 유권자는 A를 지지한다. 가능한 도착 순서는 하나뿐이고, 단 한 번의 투표 후에는 A가 앞서게 된다.