Question 9 : Odd Subarray

Find the number of distinct subarrays in an array of integers such that the sum of elements of subarray should be odd.
Note : Two subarrays are considered different if they either start or end at different index.

Constraints

1 <= Testcases <= 10 1 <= Size of Array <= 1000

Input Format :
First line will be an integer T that will denote the number of testcases
For every testcase first line will be an integer N that will denote the size of input array.
Next line will have N values separated with space that will be elements of array.


Output Format : Print the number of distinct subarrays for every testcase in a new line.

Test Case 1

Input :
1
3
1 2 3


Output : 4

Explanation 1

Total subarrays are [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]
In this there is four subarrays which sum is odd i.e: [1],[1,2] ,[2,3],[3].