An array \(B\) is called balanced if \(parity(sum(B)) = parity(lcm(B))\). Given an array \(A\) of size \(N\), find the count of balanced sub-arrays of \(A\).

As of friendly reminder,

\(parity(x)\) denotes the remainder of dividing \(x\) by \(2\)
A sub-array is the sequence of consecutive elements of the array.

Input Format:

The first line of the input contains a single integer \(T\) - the number of test cases. The description of \(T\) test cases follows.
The first line of each test case contains a single integer \(N\).
The second line contains \(N\) space-separated integers \(A_1, A_2, \ldots, A_N\).

Output Format:

For each test case print a single integer — the answer to the problem.

Constraints:

\(1 \leq T \leq 200\)
\(1 \leq N \leq 10^{5}\)
\(1 \leq A_i \leq 10^{5}\) for each valid \(i\)
The sum of \(N\) over all test cases does not exceed \(10^6\)