Epic Subarrays Counting#12271

Epic Subarrays Counting

1 second

256 megabytes

Easy

Given an array $a$ of $n$ integers, determine the count of epic subarrays.

An array is called epic if its product is strictly increasing in each step of multiplying. Formally, we call a subarray $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r to be strictly interesting at each step if and only if

a_{l} < a_{l} \cdot a_{l + 1} < a_{l} \cdot a_{l + 1} \cdot a_{l + 2} < \dots < a_{l} a_{l + 1} \dots a_{r}

a_l < a_l \cdot a_{l+1} < a_l \cdot a_{l+1} \cdot a_{l+2} < \ldots < a_l a_{l+1} \ldots a_r

Input

The first line contains single integer $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains single integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) — the length of array $a$ .

The second line of each test case contains $n$ separated integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{1}, a_{2}, \dots, a_{n} \leq 2$ 1 \le a_1, a_2, \ldots, a_n \le 2) — the array $a$ .

It's guaranteed that $\sum n \leq 1 0^{5}$ \sum n \le 10^5 overall tests.

Output

For each test case output single integer — the number of epic subarrays.

Please note! that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Examples

Example

1
3
1 2 2

Example 1

Note

In the first test case, the epic subarrays are:

$[1]$ , $[2]$ , $[2]$ because the array is single element so it's trivially increasing.
$[1, 2]$ is increasing because $1 < 1 \cdot 2$ 1 < 1 \cdot 2.
$[2, 2]$ is increasing because $2 < 2^{2}$ 2 < 2^2.
$[1, 2, 2]$ [1, 2, 2] is increasing because $1 < 2 < 2^{2}$ 1 < 2 < 2^2.

Thus the count is $6$ .

Scoring

Subtask $1$ ( $10$ points): $1 \leq \sum n \leq 1000$ 1 \le \sum n \le 1000
Subtask $2$ ( $20$ points): $a_{1} = a_{2} = \dots = a_{n}$ a_1 = a_2 = \ldots = a_n
Subtask $3$ ( $120$ points): No additional constraints.