#1562 FenceRepairing

64  5 s   128 MB  

Description

You are going to repair an old fence. The fence consists of several consecutive boards, some of which are broken and some of which are fine. The boards are numbered from left to right in increasing order. To repair all the boards between i and j, inclusive, where j is greater than or equal to i, a woodworker charges sqrt(j-i+1), where sqrt is the square root function. Due to the woodworker's pricing scheme, it is often necessary to repair boards even if they are not broken in order to get the best price.

The status of fence is given by multiple strings, so you should concatenate them into one string before calculating the repair cost.
Broken boards are represented by 'X' characters and good boards are represented by '.' characters. Print the minimal cost required to repair all broken boards.

Input

The first line of the input gives a number of test cases, T (1 <= T <= 200).
The first line of each case gives the number of status string, N (1 <= N <= 50).
Next N line gives a status of fence, F. The length of F is not greater than 50.

Output

For each test case, output the minimal cost required to repair all broken boards.
This number should be rounded three digits after the decimal point.

Sample Input

Sample Output

2
1
X.X...X.X
1
X.X.....X
3.000
2.732