Migrated from Lutece 1854 Charlie

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Charlie are given a binary string of length $N$ ( $1 \leq N \leq 2 \cdot 10^5$ ).

Now Charlie wants to cut some character so that's easy to carry.

For every step, Charlie arbitrarily find one substring 01 to delete it until not exist such substring.

Charlie wants to know the expectation of the length after cutting.

Input

The first line is an integer $T$($1 \leq T \leq 68$), which indicates the number of testcases.

For each testcase:

The first line of the input file contains the integer $N$.

The second line contains the binary string $s$ of length $N$, consisting of letters 0 and 1 only.

Output

For each testcase, your program should output the expectation of the length of the remain string. The answer should keep three decimal digits.

Samples

1
4
1101

2.000

1
6
010101

0.000

Resources

The 16th UESTC Programming Contest Preliminary