Chefu is Chef's little brother, he is 12 years old and he is new to competitive programming.
Chefu is practicing very hard to become a very skilled competitive programmer and win gold medal in IOI.
Now Chefu is participating in a contest and the problem that he is trying to solve states:
Given an array A of N integers, find any i, j such that i <  j 
and Ai + Aj is maximum possible 
unfortunately, there's no much time left before the end of the contest, so Chefu doesn't have time to think of correct solution, so instead, he wrote a solution that selects a random pair (i,  j) (i <  j) and output Ai + Aj. each pair is equiprobable to be selected.
Now Chefu wants your help to calculate the probability that his solution will pass a particular input.

-----Input-----
First line contains an integer T denoting the number of test-cases.
First line of each test-case contains a single integer N
Second line of each test-case contains N space-separated integers A1 A2 ... AN

-----Output-----
For each test-case output a single line containing a single number denoting the probability that Chefu's solution to output a correct answer. your answer will be accepted if the absolute difference between it and correct answer is less than 1e-6

-----Constraints-----
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 100
- 1 ≤ Ai ≤ 1,000

-----Example-----
Input:
3
4
3 3 3 3
6
1 1 1 2 2 2
4
1 2 2 3

Output:
1.00000000
0.20000000
0.33333333

Difficulty: interview

Starter code:

Solutions:
T=int(input())
for i in range(T):
 N=int(input())
 A=list(map(int,input().split()))[:N]
 l=[]
 for j in range(len(A)):
  for k in range(j+1,len(A)):
   l.append(A[j]+A[k])
 print(l.count(max(l))/((N*(N-1))/2))

for i in range(int(input())):
 n=int(input())
 t=list(map(int,input().split()))[:n]
 m=[]
 for j in range(len(t)):
  for k in range(j+1,len(t)):
   m.append(t[j]+t[k])
 print(m.count(max(m))/((n*(n-1))/2))

t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))[:n]
 l=[]
 for j in range(len(a)):
  for k in range(j+1,len(a)):
   l.append(a[j]+a[k])
 print(l.count(max(l))/((n*(n-1))/2))

T=int(input())
for i in range(T):
 N=int(input())
 A=list(map(int,input().split()))[:N]
 l=[]
 for j in range(len(A)):
  for k in range(j+1,len(A)):
   l.append(A[j]+A[k])
 print(l.count(max(l))/((N*(N-1))/2))


# cook your dish here

for i in range(int(input())):
 N=int(input())
 l=list(map(int,input().split()))[:N]
 sum=l[N-1]+l[N-2]
 count=0
 max=0
 for i in range(len(l)):
  for j in range(i+1,len(l)):
   if l[i]+l[j]>max:
    max=l[i]+l[j]
    
 for i in range(len(l)):
  for j in range(i+1,len(l)):
   s=l[i]+l[j]
   if s==max:
    count+=1
 f=N*(N-1)/2
 
 print(format(count/f,'.8f'))
   
 


t=int(input())
while t:
 n=int(input())
 l=list(map(int,input().split()))
 max=0
 c=0
 for i in range(n):
  for j in range(i+1,n):
   if l[i]+l[j]>max:
    max=l[i]+l[j]
 for i in range(n):
  for j in range(i+1,n):
   if l[i]+l[j]==max:
    c+=1
 x=n*(n-1)/2
 print(c/x)
 t-=1

# cook your dish here
t=int(input())
while t>0:
 n=int(input())
 a=list(map(int,input().split()))
 max=0
 c=0
 for i in range(n):
  for j in range(i+1,n):
   if a[i]+a[j]>max:
    max=a[i]+a[j]
 for i in range(n):
  for j in range(i+1,n):
   if a[i]+a[j]==max:
    c+=1
 x=n*(n-1)/2
 print(c/x)
 t-=1

for _ in range(int(input())):
 n = int(input())
 a = sorted(list(map(int, input().split())), reverse=True)
 i = 1
 while i<n-1 and a[i]==a[i+1]:
  i+=1
  
 if a[0] == a[1]:
  print(i*(i+1)/(n*(n-1)))
 else:
  print(2*i/(n*(n-1)))

# def main():
#     t=int(input())
#     while(t!=0):
#         n = int(input())
#         arr = list(map(int, input().split()))
#         maxVal=-1
#         for i in range(0,n):
#             for j in range(i+1,n):
#                 temp =arr[i]+arr[j]
#                 if(maxVal<temp):
#                     maxVal=temp
#
#         count=0
#         for i in range(0,n):
#             for j in range(i+1,n):
#                 temp =arr[i]+arr[j]
#                 if(maxVal==temp):
#                     count+=1
#         val = (n*(n-1))/2
#         print(count/val)
#         t=t-1
#
# def __starting_point():
#     main()


def main():
 t=int(input())
 while(t!=0):
  n = int(input())
  arr = list(map(int, input().split()))
  arr.sort()
  maxEle = arr[n-1]
  num = (n*(n-1))/2
  count1= arr.count(maxEle)

  if(count1==1):
   count2=arr.count(arr[n-2])
   print(count2/num)
  else:
   val = (count1*(count1-1))/2
   print(val/num)
  t=t-1

def __starting_point():
 main()
__starting_point()

def main():
 t=int(input())
 while(t!=0):
  n = int(input())
  arr = list(map(int, input().split()))
  maxVal=-1
  for i in range(0,n):
   for j in range(i+1,n):
    temp =arr[i]+arr[j]
    if(maxVal<temp):
     maxVal=temp

  count=0
  for i in range(0,n):
   for j in range(i+1,n):
    temp =arr[i]+arr[j]
    if(maxVal==temp):
     count+=1
  val = (n*(n-1))/2
  print(count/val)
  t=t-1

def __starting_point():
 main()
__starting_point()

# cook your dish here
#number of test cases
for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 l=[]
 for i in range(n):
  for j in range(i+1,n):
    l.append(a[i]+a[j])
 print(l.count(max(l))/len(l))

# cook your dish here
try:
 T=int(input())
 for _ in range(T):
  N=int(input())
  A=list(map(int,input().split()))
  c=0
  d=[]
  for i in range(N):
   for j in range(i+1,N):
    d.append(A[i]+A[j])
  ans=d.count(max(d))/len(d)
  print('%0.8f'%ans)
except:
 pass

for _ in range(int(input())):
 K = int(input())
 arr = list(map(int, input().split()))
 P = []
 for i in range(K):
  for j in range(i+1,K):
   P.append(arr[i]+arr[j])
 print(P.count(max(P))/len(P))




# cook your dish here
for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 l=[]
 for i in range(n):
  for j in range(i+1,n):
    l.append(a[i]+a[j])
 print(l.count(max(l))/len(l))

for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 l=[]
 for i in range(n):
  for j in range(i+1,n):
    l.append(a[i]+a[j])
 print(l.count(max(l))/len(l))

t = int(input())

for _ in range(t):
 n = int(input())
 
 a = [int(x) for x in input().split()]
 f = []
 
 for i in range(n):
  for j in range(i+1, n):
   f.append(a[i]+a[j])
 
 maxi = f.count(max(f))
 ans = maxi/len(f)
 
 print(format(ans, '.6f'))

# cook your dish here
try:
 for _ in range(int(input())):
  n=int(input())
  l=list(map(int,input().split()))
  p=[]
  for i in range(n):
   for j in range(i+1,n):
    p.append(l[i]+l[j])
  m=p.count(max(p))/len(p)
  print('%.8f'%m)
except:
 pass

# cook your dish here
try:
 T=int(input())
 for _ in range(T):
  N=int(input())
  A=list(map(int,input().split()))
  c=0
  d=[]
  for i in range(N):
   for j in range(i+1,N):
    d.append(A[i]+A[j])
  ans=d.count(max(d))/len(d)
  print('%0.8f'%ans)
except:
 pass

# cook your dish here
from itertools import combinations

t=int(input())

def pair(arr):
 maxi=0
 k=0
 d=0
 if len(set(arr))==1:
  return "{:.8f}".format(1)
 c=list(combinations(arr,2))
 
 for i in c:
  if sum(i) > maxi:
   maxi=sum(i)
  d+=1 
 
 for i in c:
  
  if sum(i) == maxi:
   k+=1
 p=k/d
 
 
 return "{:.8f}".format(p)
 
  

for _ in range(t):
 
 n=int(input())
 arr=list(map(int,input().split()))
 r=pair(arr)
 print(r)

# cook your dish here
t = int(input())

while t:
 N = int(input())
 A = list(map(int, input().split()))
 l = []

 for i in range(N):
  for j in range(i+1, N):
   l.append(A[i]+A[j])

 c = l.count(max(l))

 print(c/len(l))

 t = t-1


# cook your dish here
for _ in range(int(input())):
 N = int(input())
 A = list(map(int,input().split()))
 B = []
 for i in range(N-1):
  for j in range(i+1,N):
   B.append(A[i]+A[j])
 C = max(B)
 D=N*(N-1)//2
 count = B.count(C)
 print('%0.8f' %(count/D))

t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 list1=[]
 for i in range(n-1):
  for j in range(i+1,n):
   list1.append(a[i]+a[j])
 c=0
 c=max(list1)
 d=0
 d=n*(n-1)//2
 c1=0
 c1=list1.count(c)
 print(c1/d)


for _ in range(int(input())):
 N = int(input())
 L = list(map(int, input().split()))
 
 L_copy = L.copy()
 N1 = max(L_copy)
 L_copy.remove(N1)
 N2 = max(L_copy)
 
 req_out = 0
 for i in range(N):
  for j in range(N):
   if i != j and ((L[i]==N1 and L[j]==N2) or (L[i]==N2 and L[j]==N1)):
    req_out += 1
 
 tot_out = N * (N-1) / 2
 
 print(req_out / (2 * tot_out))

# cook your dish here
try:
 t = int(input())
 for _ in range(t):
  n = int(input())
  arr = list(map(int,input().split()))
  from itertools import combinations
  ans = []
  for l in combinations(arr,2):
   ans.append(l)
  maxx = 0
  for l in ans:
   m = sum(l)
   if m>maxx:
    maxx = m
  count = 0 
  for l in ans:
   item = sum(l)
   if item<maxx:
    count+=1
  print(1 - count/len(ans))
  continue
except:
 pass