In ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed X problems during the contest, and submitted Y times for these problems, then the ''Dirt Ratio'' is measured as XY. If the ''Dirt Ratio'' of a team is too low, the team tends to cause more penalty, which is not a good performance.
Picture from MyICPC
Little Q is a coach, he is now staring at the submission list of a team. You can assume all the problems occurred in the list was solved by the team during the contest. Little Q calculated the team's low ''Dirt Ratio'', felt very angry. He wants to have a talk with them. To make the problem more serious, he wants to choose a continuous subsequence of the list, and then calculate the ''Dirt Ratio'' just based on that subsequence.
Please write a program to find such subsequence having the lowest ''Dirt Ratio''.
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there is an integer n(1≤n≤60000) in the first line, denoting the length of the submission list.
In the next line, there are n positive integers a1,a2,...,an(1≤ai≤n), denoting the problem ID of each submission.
For each test case, print a single line containing a floating number, denoting the lowest ''Dirt Ratio''. The answer must be printed with an absolute error not greater than 10−4.
1 2 1 2 3
- Dirt Ratio