All Submissions


Problem Specification

Bilbo Baggins, a burglar in the company of 13 dwarves, has unfortunately been separated from the others. While looking for a way out of the tunnels of the Misty Mountains he meets Gollum. But Gollum doesn't want to help Bilbo, he wants to eat him! So they decide to play a game.
Gollum has N wooden sticks in his tunnel, all of different lengths. Bilbo has to choose any 3 sticks at random and has to give them to Gollum. If Gollum is unable to form a triangle Bilbo will win the game and Gollum will show him the way out. Otherwise, Gollum will eat him.

Given the lengths of the N wooden sticks, find the probability that Bilbo wins the game.

Input Specification

The first line of input indicates the number of test cases, t. Each test case will have 2 lines, the first line indicates n, the number of wooden sticks Gollum has, and the next line indicates the n space separated lengths of the sticks.
Output Specification:

The Output for each test case is a single decimal value between 0 and 1 indicating the probability that Bilbo wins the game in that instance. The value should be precise upto 4 decimal places.

Sample Input


3
5
1 6 7 2 5
6
8 3 15 4 9 20
7
1 4 8 6 19 12 10


Sample Output


0.4000
0.7500
0.6857


Constraints

1<=t<=200
3<=n<=2,000
Length of a stick l must be between 1 and 1,000,000

Note : If the 3 sticks chosen by Bilbo form a degenerate triangle he will not win. A degenerate triangle is one where one side is exactly equal to the sum of the other two sides. For example, sticks of lengths 1,2 and 3 form a degenerate triangle because 1+2=3.

Problem Setter : Neesha Sinha

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0