For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,

$F(A) = \sum_{L=1}^N \sum_{R=L}^N (\prod_{i=L}^R A_{i}\right )$

For example, let A = [1, 0, 1], then there are 6 possible subarrays:

Subarray [1, 1] has product = 1
Subarray [1, 2] has product = 0
Subarray [1, 3] has product = 0
Subarray [2, 2] has product = 0
Subarray [2, 3] has product = 0
Subarray [3, 3] has product = 1

So F(A) = 1+1 = 2.

Given a binary array A, determine the value of F(A).

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N denoting the length of the array.
• The second line contains N space-separated integers denoting the array A.

------ Output Format ------

For each test case, output on a new line the value of F(A).

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 1$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
4
3
1 0 1
1
0
2
1 1
4
1 1 0 1

----- Sample Output 1 ------
2
0
3
4

----- explanation 1 ------
Test case $1$: Explained in the statement.

Test case $2$: There is only $1$ subarray and it has product $= 0$.

Test case $3$: All the $3$ subarrays have product $= 1$.

见题面

见题面