hyz认为，如果存在某个元素可以表示为所有其他元素之和(如果没有其他元素，则所有其他元素之和为0)，那么这个数组就是好数组。

例如，数组 [1,6,3,2][1,6,3,2] 是好数组，因为 1+3+2=61+3+2=6 。此外，数组 [0][0] 也是好数组。

然而，数组 [1,2,3,4][1,2,3,4] 和 [1][1] 却不是好数组。

亚历克斯有一个数组 a1,a2,…,ana1,a2,…,an 。帮他计算数组 aa 的非空前缀的个数。

换句话说，数出有多少个整数 ii ( 1 ≤ i ≤ n1≤i≤n )，长度为 ii 的前缀(即 a1,a2,…,aia1,a2,…,ai )是好的

输入的第一行包含一个整数 tt  ( 1 ≤ t ≤ 5000) - 测试用例的数量。

每个测试用例的第一行包含一个整数 nn ( 1 ≤ n ≤ 200000) - 数组中的元素个数。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,an(0 ≤ ai ≤ 1000000000) 数组中的元素。

保证所有测试用例中 nn 的总和不超过 200000 。