We are given a sequence S of N distinct integers. Denote by S[i] as ith element of S.

Hardik picks up a random permutation of S , breaks it into product of disjoint cycles & looks at cycle containing S[i].He notes down the sum of all element of this cycle. Call the expected value of this sum as cycleSum[i]. Your task is to find the minimum value amongst all cycleSums.

Assume all permutations of these N numbers are equally likely.

Input

First line contains an integer T which denotes the number of test cases. Then follow description of T test cases. Each test case takes 2 lines. First line contains a single integer N, the size of S. Then follows second line containing N elements of S.

Output

Print the answer for each test case, rounded to exactly one decimal place, in one line each.

Example

Input:
2
1
1
2
1 2

Output:
1.0
2.0

Note
Notion of cycles for any sequence is defined by using index in the sequence (1-N).

Explanation of Examples

In first case only possible permutation is (1) So answer is trivially 1.0

In second case possible permutations are (1)(2) and (12). As both of these are equally likely, cycleSum[1] = 1/2 * 1 + 1/2 * (1+2) = 2.0

And cycleSum[2] = 1/2 * 2 + 1/2 * (1+2) = 2.5. Smaller of these is 2.0, hence the answer.

Constraints

1 ≤ T ≤ 500
1 ≤ N ≤ 5000
All elements of S are distinct integers in range 0 to 10⁵