Create Some Walls!

Mahdi has finally found some time to build his dream house. He had been looking for some cool designs, but all the designs he found disappointed him. During this time of disappointment, he got an idea! Why not design the house with some randomness?

Mahdi starts with a $ L \times W $ axis parallel rectangle representing the outer walls of his home. Then he builds $ n $ walls inside the house, creating $ n+1 $ rooms. He does this by taking a string $ s $ of length $ n $ which consists only of 'H' and 'V'. After that, he follows the following procedure: for the $ i $-th wall, he looks at $ s[i] $. He chooses one of the $ i+1 $ already created rooms randomly and then in that chosen room he builds a vertical or horizontal wall according to whether $ s[i] $ is 'V' or 'H'. He chooses the positioning of this random wall completely uniformly from all possible walls that can be built in that room. This means that the wall's coordinates are not necessarily integers.

To help you understand the process better, here is an example. Suppose $L = 10$, $W = 5$ and the string is 'HHV', then these 4 pictures are the states of the room before putting any walls and then putting the 3 walls:

The red walls were built in random positions in randomly chosen rooms.

Mahdi has already built the outer 4 walls, but is curious about how many bricks he will need for the interior randomly made walls. So, you have to output the expected total length of the interior walls or in other words, the expected total length of the red walls in the figure.

Input

Input will consist of multiple testcases. The first line will contain an integer $ T (1 \leq T \leq 10^5) $, the number of testcases.

Each testcase will consist of two lines. The first line will contain three space-separated integers, $L, W$ and $n (1 \leq L, W \leq 1000; 1 \leq n \leq 10^5)$, the length, width and the number of walls, respectively. The next line will contain a string of length $n$ consisting of only V and W.

Sum of $n$ over all testcases will not exceed $10^5$.

Output

For each testcase, output the expected total length of the interior walls in a line. Your answer will be considered correct if its absolute difference or relative difference with the judge's answer is at most $ 10^{-8} $. Formally, if your output is $A$ and judge's output is $B$, then your answer will be considered correct if $\frac{|A-B|}{\max(1, B)} \leq 10^{-8}$.

Sample

3
10 5 3
HHV
10 20 1
H
5 5 3
HVH

13.333333333
20.000000000
10.833333333