Given an array $A$ of $N$ integers.

Find the count of subarrays whose product of elements is a perfect cube.

Input Format:

• First line contains an integer $N$.
• Next line contains $N$ space-separated integers denoting the array elements.

Output Format:

Print the number of subarrays whose product of elements is a perfect cube.

Constraints:

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