- Prepare
- Mathematics
- Probability
- The Matchstick Experiment

# The Matchstick Experiment

# The Matchstick Experiment

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.