Dirt Ratio

Problem Description

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 $\frac{X}{Y}$. 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''.

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases. In each test case, there is an integer $n(1\leq n\leq 60000)$ in the first line, denoting the length of the submission list. In the next line, there are $n$ positive integers $a_1,a_2,...,a_n(1\leq a_i\leq n)$, denoting the problem ID of each submission.

Output

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}$.

Sample Input

1

5

1 2 1 2 3

Sample Output

0.5000000000

Hint

For every problem, you can assume its final submission is accepted.

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6070