Coin Toss

In a popular carnival game, a coin is tossed onto a table covered with square tiles arranged in a grid. The prize depends on how many tiles the coin covers when it comes to rest: the more tiles it covers, the better the prize. The diagram below shows the results of five coin tosses:

In this example:

• coin 1 covers 1 tile
• coin 2 covers 2 tiles
• coin 3 covers 3 tiles
• coin 4 covers 4 tiles
• coin 5 covers 2 tiles

A coin is allowed to land on the boundary of the playing area (coin 5). For a coin to cover a tile, it must overlap a positive area of that tile; merely touching the tile's boundary does not count. The center of the coin lands at a uniformly random point of the playing area (boundary included). You may assume that (1) the coin always comes to rest lying flat, and (2) the player is skilled enough that the center of the coin always comes to rest inside the playing area or on its boundary.

The probability of covering a given number of tiles depends on the tile size, the coin size, and the number of rows and columns of tiles. Write a program that computes these probabilities.

The first line contains an integer: the number of test cases.

Each test case is a single line with four integers $m$, $n$, $t$, and $c$ separated by spaces. The playing area has $m$ rows and $n$ columns of tiles, and each tile is a square of side length $t$. The coin's diameter is $c$.

Constraints: $1 \le m, n \le 5000$ and $1 \le c < t \le 1000$.

For each test case, print the case number on its own line, followed by four lines giving the probability that the coin covers 1, 2, 3, and 4 tiles, in that order. Each probability is a percentage rounded to 4 decimal places, printed in the exact format shown in the examples. Perform the calculations with double-precision floating-point numbers. A value that rounds to zero must be printed as 0.0000, never with a negative sign.

Separate the output of consecutive test cases with a blank line.