ravi and nithish

from math import isqrt
from collections import Counter

# Precompute perfect squares and cubes up to max_sum
MAX_SUM = 2 * 10**9

perfect_squares = set()
i = 1
while i * i <= MAX_SUM:
    perfect_squares.add(i * i)
    i += 1

perfect_cubes = set()
i = 1
while i * i * i <= MAX_SUM:
    perfect_cubes.add(i * i * i)
    i += 1

def is_perfect(x):
    return x in perfect_squares or x in perfect_cubes

def count_perfect_pairs(arr):
    freq = Counter(arr)
    keys = sorted(freq.keys())
    count = 0
    
    for i, x in enumerate(keys):
        for y in keys[i:]:
            total = x + y
            if is_perfect(total):
                if x == y:
                    # count combinations: nC2 = n*(n-1)/2
                    count += freq[x] * (freq[x] - 1) // 2
                else:
                    count += freq[x] * freq[y]
    return count

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        arr = list(map(int, input().split()))
        print(count_perfect_pairs(arr))

if __name__ == "__main__":
    main()