동전 던지기

인기 있는 축제 게임에서, 정사각형 타일이 격자 모양으로 깔린 탁자 위로 동전을 던진다. 동전이 멈췄을 때 덮고 있는 타일의 개수에 따라 상품이 정해지며, 더 많은 타일을 덮을수록 더 좋은 상품을 받는다. 아래 그림은 동전을 다섯 번 던진 결과를 보여 준다.

이 예시에서:

• 동전 1은 타일 1개를 덮는다
• 동전 2는 타일 2개를 덮는다
• 동전 3은 타일 3개를 덮는다
• 동전 4는 타일 4개를 덮는다
• 동전 5는 타일 2개를 덮는다

동전이 게임 영역의 경계에 걸쳐 놓여도 된다(동전 5). 동전이 어떤 타일을 "덮는다"고 하려면 그 타일과 양(positive)의 넓이만큼 겹쳐야 한다. 즉 타일의 경계에 닿기만 해서는 안 된다. 동전의 중심은 게임 영역(경계 포함) 안의 한 점에 균등한 확률로 놓인다. 또한 (1) 동전은 항상 평평하게 눕고, (2) 던지는 사람이 충분히 능숙하여 동전의 중심은 항상 게임 영역 내부 또는 경계 위에 멈춘다고 가정한다.

특정 개수의 타일을 덮을 확률은 타일 크기, 동전 크기, 그리고 타일의 행과 열의 수에 따라 달라진다. 이 확률들을 계산하는 프로그램을 작성하여라.

첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다.

각 테스트 케이스는 공백으로 구분된 네 정수 $m$, $n$, $t$, $c$로 이루어진 한 줄이다. 게임 영역은 $m$개의 행과 $n$개의 열의 타일로 이루어지며, 각 타일은 한 변의 길이가 $t$인 정사각형이다. 동전의 지름은 $c$이다.

제약: $1 \le m, n \le 5000$, $1 \le c < t \le 1000$.

각 테스트 케이스에 대해 케이스 번호를 한 줄에 출력하고, 이어서 동전이 타일을 1개, 2개, 3개, 4개 덮을 확률을 순서대로 각각 한 줄씩 출력한다. 각 확률은 백분율로 나타내며 소수점 아래 넷째 자리까지 반올림하고, 예시에 나온 형식과 정확히 같게 출력한다. 계산은 배정밀도 부동소수점 수로 수행한다. 반올림한 값이 0이면 음의 부호 없이 0.0000으로 출력해야 한다.

연속한 테스트 케이스의 출력은 빈 줄로 구분한다.