리스크

블라디미르와 마크가 전략 보드게임 리스크를 한다. 플레이어는 세계의 지역을 점령하고 대륙 전체를 차지하는 것을 목표로 한다. 마크는 군대 $M$개가 있는 지역을 가지고 있고, 블라디미르가 군대 $N$개로 지키는 인접 지역을 공격하려 한다. 마크가 더 약한 쪽이라서, 이 전투에서 자신이 이길 확률을 알고 싶어 한다.

전투는 리스크의 표준 규칙을 따르되 한 가지가 다르다. 주사위가 꼭 육면체일 필요는 없다. 주사위는 면이 $D$개이고 ($D \ge 1$), 각 면의 값은 모두 다르며, 어느 면이든 나올 확률이 같다.

전투는 여러 라운드로 이루어진다. 공격 측이 공격을 시작하는 지역에 군대 $A$개를 두고 있고, 방어 측이 자기 지역에 군대 $B$개를 두고 있다고 하자. 한 라운드는 다음 순서로 진행된다.

1. 공격 측이 주사위를 $\min(3, A - 1)$개 굴린다. 원칙적으로 주사위 세 개를 쓰지만 군대 한 개는 지역에 남아 공격에 참여하지 않으므로, $A < 4$이면 $A - 1$개만 굴린다.
2. 방어 측은 공격 측이 굴린 눈을 보고 나서 주사위를 굴린다. $B = 1$이면 한 개를 굴린다. $B \ge 2$이면 전투 전체에서 자신이 이길 확률이 가장 커지도록 한 개와 두 개 중에서 고른다.
3. 두 사람이 굴린 주사위 개수 중 작은 쪽을 $c$라고 하자. 양쪽의 가장 큰 눈끼리 비교하고, $c = 2$이면 두 번째로 큰 눈끼리도 비교한다. 각 비교에서 값이 큰 쪽이 이기고, 값이 같으면 방어 측이 이긴다. 비교에서 진 쪽은 자기 지역에서 군대를 한 개 잃는다. 남는 주사위는 무시한다.

공격 측의 군대가 한 개만 남으면 방어 측이 이기고, 방어 측의 군대가 하나도 남지 않으면 공격 측이 이긴다. 둘 중 하나가 일어나면 전투가 끝난다.

예를 들어 공격 측이 주사위 세 개를 굴려 4, 2, 1이 나오고 방어 측이 두 개를 굴려 3, 2가 나왔다고 하자. 첫 번째 비교는 4와 3이므로 공격 측이 이기고, 두 번째 비교는 2와 2이므로 방어 측이 이긴다. 그래서 양쪽 모두 군대를 한 개씩 잃는다. 다른 예로 공격 측의 큰 눈 두 개가 모두 최댓값 $D$이면, 방어 측은 주사위를 한 개만 굴리는 편이 낫다. 그러면 잃는 군대가 많아야 한 개다.

블라디미르는 규칙도 주사위도 알고 있고, 마크가 전투에서 이길 확률이 가장 작아지도록 방어한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 주어진다.

• 첫 줄에 주사위 면의 개수 $D$가 주어진다. ($1 \le D \le 20$)
• 둘째 줄에 마크의 지역에 있는 군대 수 $M$과 블라디미르의 지역에 있는 군대 수 $N$이 공백으로 구분되어 주어진다. ($2 \le M \le 100$, $1 \le N \le 100$)

각 테스트 케이스마다 마크가 전투에서 이길 확률을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 지수 표기법은 쓰지 않는다.