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\)