In an grid, matchsticks are placed at the boundaries between cells. For example, if and , the matchsticks are placed in the following way:
The Experiment
For each of the matchsticks, remove it with probability .
We define a connected component to be a maximal set of cells not isolated from one another by matchsticks. We calculate our as the number of connected components in the grid with cells, divided by .
For example, suppose our grid looks like this after performing the first step:
To calculate our , we need to first find the number of connected components having cells. The diagram below counts all such components consisting of connected cells:
As you can see, there are connected components of size . From this, we perform the following calculation:
You are given queries where each query consists of , , and . For each query, find and print the expected value of on a new line.
Need Help? Check out this learning aid explaining some important properties of expected values.
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains three space-separated integers describing the respective values of integer , integer , and real number .
Constraints
- is a real number scaled to two decimal places (e.g., ).
Subtask
- For of the total score,
Output Format
For each query, print a single real number on a new line denoting the answer to the query. Any answer having an absolute error within of the true answer is acceptable.
Sample Input 0
2
2 2 0.50
2 3 0.75
Sample Output 0
0.4375000000
0.0810546875000
Explanation 0
We can verify our answer by performing several brute-force simulations of the experiment and then averaging the scores.