You are given an array $A$ containing $N$ elements. Your task is to find the number of subarrays with even products.

A subarray of an array can be obtained by deleting any prefixes and suffixes.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the number of elements in array $A$.
• The second line of each test case contains $N$ space-separated integers of array $A$.

Output format

For each test case, print a single line denoting subarrays with even products.

Constraints

$1 \leq T \leq 20000$

$1 \leq N \leq 200000$

$1 \leq A_i \leq 1e9 \forall i \in [1,N]$

Sum of $N$ over all test cases does not exceed 200000