C. Odd Subbarray
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers, we call a subarray good if its product has an odd number of divisors.

In other words, subarray $$$a[l...r]$$$ $$$(1 \leq l \leq r \leq n)$$$ is good iff $$$(\prod_{i = l}^{r}a_i)$$$ has an odd number of divisors.

You're asked to count the number of good subarrays in the array $$$a$$$.

Input

The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ – the number of test cases.

Each test case has two lines, the first being one integer $$$n$$$ $$$(1 \leq n \leq 2\times10^5)$$$ – the length of the array.

The second line of the test cases is $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 300)$$$ – the elements of the array.

It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

Output

Print one integer for each test case, the number of good subarrays in the array.

Example
Input
2
4
1 2 4 2
3
1 1 1
Output
4
6