three-sum-monk

This time, there will be no unnecessary information in the problem statement.

Given an array(A) of N integers, find the probability that sum of any selected triplet is a cube of an integer number.

A triplet is a set of any three indices. Two triplets with same indices but in different order are considered same (Ex: triplets with indices {2,4,5} and {2,5,4} are same).

Cube of a number x is x * x * x.

Input:

First line has an integer T=number of test cases.
Each test case has two lines.
First line of test case has an integer N=numbers in the array.
Second line of test case has an array of N integers.

Output:

Print answer for each test case in a separate lines with exactly 9 decimal digits.  

Constraints:

1 ≤ T ≤ 40
3 ≤ N ≤ 500
1 ≤ Ai ≤ 2000  

SAMPLE INPUT
2
4
2 3 4 6
4
1 1 6 25

SAMPLE OUTPUT
0.000000000
0.500000000

Explanation

Case #1 : No triplet sum could be cube of an integer.

Case #2 : We can form 4 triplets.

Indices        Values       Sum  
{1,2,3}        {1,1, 6}    1+1+6 = 8  
{1,2,4}        {1,1,25}    1+1+25 = 27  
{1,3,4}        {1,6,25}    1+6+25 = 32
{2,3,4}        {1,6,25}    1+6+25 = 32

Out of 4 resulting sums, 2 are cube of a number and therefore probability is 2/4.

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics

Probability


Solutions: