Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Game of Sticks

By saif_sust · Limits 1s, 512 MB

Bob and Alice are two friends. They always play very strange game. Today they are playing another strange game.

There are two phases in this game. In the first phase, Alice placed N sticks in a straight line. Then in the second phase, Bob brought his Giant Fan in front of the straight line and switched on it. If all the sticks placed by Alice fall, Bob will win this game. Otherwise, Alice will be the winner.

You are a very smart person and somehow collect the falling probability (P) for each stick. Now you want to impress Alice by telling her winning probability.

Input

Input starts with an integer T (T ≤ 105) denoting the number of test cases.

Each test case starts with an integer N (1 ≤ N ≤ 105), the number of sticks.

Next line contains N real numbers P1, P2, P3... PN denoting the falling probability of each stick.

0.0 ≤ Pi ≤ 1.0 for all i from 1 to N

You can assume that sum of all N from each test case will not cross 106 .

Output

For each case, print the winning probability of Alice in a single line. Print exactly 5 digits after decimal point.

Sample

InputOutput
1
4
0.5 0.5 0.5 0.5

0.93750


Statistics

94% Solution Ratio

as8.09Earliest, Jul '17

MutasimFastest, 0.2s

DayamoyLightest, 393 kB

silenced.VOICEShortest, 126B