#N. JIXMPII5JUhKSP0#;$+

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

Alex thinks some array is good if there exists some element that can be represented as the sum of all other elements (the sum of all other elements is $0$ if there are no other elements). For example, the array $[1,6,3,2]$ is good since $1+3+2=6$ . Furthermore, the array $[0]$ is also good. However, the arrays $[1,2,3,4]$ and $[1]$ are not good.

Alex has an array $a_1,a_2,\ldots,a_n$ . Help him count the number of good non-empty prefixes of the array $a$ . In other words, count the number of integers $i$ ( $1 \le i \le n$ ) such that the length $i$ prefix (i.e. $a_1,a_2,\ldots,a_i$ ) is good.

Format

Input

The first line of the input contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $0 \le a_i \le 10^9$ ) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

Output

For each test case, output a single integer — the number of good non-empty prefixes of the array $a$ .

Sample

7
1
0
1
1
4
1 1 2 0
5
0 1 2 1 4
7
1 1 0 3 5 2 12
7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296
10
0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592

ShanghaiTech ACM 炸鱼杯

未参加

状态: 已结束
规则: OI
题目: 46
开始于: 2024-12-10 23:00
结束于: 2024-12-15 13:00
持续时间: 110 小时
主持人: _Arahc_
参赛人数: 112

#N. JIXMPII5JUhKSP0#;$+

JIXMPII5JUhKSP0#;$+

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

#N. JIXMPII5JUhKSP0#;$+

JIXMPII5JUhKSP0#;$+

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

还没有账户？

登录