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 ≤ A_i ≤ 2000