You are given an array \(A\) of \(N\) integers. Find the number of subarrays that satisfy the following condition:

• The product of numbers in the subarray is a perfect cube, that is, there exists a positive integer \(x\) such that \(x^3 = P\) where \(P\) is the product of numbers in the subarray.

Input format

• The first line contains an integer \(T\) denoting the number of test cases.
• The first line of each test case contains an integer \(N\) denoting the number of elements in the array.
• The next line of each test case contains \(N\) space-separated integers denoting the array elements.

Output format

For each test case, print the number of subarrays that satisfy the provided condition in a new line.

Constraints