You are given an array $$A$$ of $$N$$ integers. You need to count the subarrays which have the sum of all elements in it a perfect square.

Input
The first line contains an integer $$N$$ that denotes count of elements in the array. Next line contains $$N$$ space separated integers that denote elements of the array.

Output
In the output, you need to print the count of subarrays for which the sum of elements is a perfect square.

Constraints
$$1 \le N \le 5000$$
$$1 \le A[i] \le 10^6$$