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

$1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 1 \le A[i] \le 100$