Problem Description

度度熊打算学习一下虚拟码。假设数组 (array) 的索引 (index) 从 $0$ 开始，考虑以下的虚拟码：


Input:

$A_{in}$: an integer array

$L$: an integer

$R$: an integer

Output:

$A_{out}$: an integer array

Program:

$A_{out}$ := an empty array

$x$ := $0$

for $i$ := $L$ to $R$ do

    if $A_{in}$[$i$] is $0$

        append $x$ to the end of $A_{out}$

    else

        add $A_{in}$[$i$] to $x$

output $A_{out}$


例如，假设 $A_{in} = [1, 3, 0, -2, 0, 0], L = 1, R = 4$，执行以上虚拟码的结果 $A_{out} = [3, 1]$。

现在给定一个长度为 $N$ 的整数数组 $A_{in}$，请问有多少组不同的整数数对 $(L, R)$，满足下列条件：

1. $0 \le L \le R < N$
2. 将 $A_{in}, L, R$ 作为以上虚拟码的输入，执行结果的 $A_{out}$ 为一个非空的数组。
3. 承上，如果将 $A_{out}$ 视作一个数列，它是一个首项及公比都非 $0$ 的等比数列。

举例而言，$[-100], [2, 2], [1, 2, 4], [8, -12, 18]$ 都是在这题中合法的等比数列，而 $[0], [0, 1], [6, 0, 0], [1, 2, 3]$ 都不是。

Input

输入的第一行有一个正整数 $T$，代表接下来有几笔测试资料。

对于每笔测试资料：
第一行有一个正整数 $N$。
接下来的一行有 $N$ 个整数 $x_i$，代表给定的数组$A_{in}$。

* $1 \le N \le 3.5 \times 10^5$
* $-10^8 \le x_i \le 10^8$
* $1 \le T \le 24$
* 至多 $4$ 笔测试资料中的 $N > 3000$

Output

对于每一笔测试资料，请依序各自在一行内输出一个整数，代表符合条件的$(L, R)$ 对数的数量。

2
5
1 0 1 0 1
9
1 0 1 0 1 -3 4 0 4

6
20