C. Хорошие префиксы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алекс считает, что некоторый массив является хорошим, если существует элемент, который является суммой всех других элементов (сумма всех других элементов равна $$$0$$$, если других элементов нет). Например, массив $$$[1,6,3,2]$$$ является хорошим, так как $$$1+3+2=6$$$. Кроме того, массив $$$[0]$$$ также является хорошим. Однако массивы $$$[1,2,3,4]$$$ и $$$[1]$$$ не являются хорошими.

У Алекса есть массив $$$a_1,a_2,\ldots,a_n$$$. Помогите ему посчитать количество хороших непустых префиксов массива $$$a$$$. Другими словами, посчитайте количество целых чисел $$$i$$$ ($$$1 \le i \le n$$$), для которых префикс длины $$$i$$$ (т.е. $$$a_1,a_2,\ldots,a_i$$$) является хорошим.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество хороших непустых префиксов массива $$$a$$$.

Пример
Входные данные
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
Выходные данные
1
0
3
3
4
1
2
Примечание

В четвертом примере массив имеет пять префиксов:

  • префикс $$$[0]$$$ является хорошим массивом, как упоминается в условии;
  • префикс $$$[0, 1]$$$ не является хорошим массивом, так как $$$0 \ne 1$$$;
  • префикс $$$[0, 1, 2]$$$ не является хорошим массивом, так как $$$0 \ne 1 + 2$$$, $$$1 \ne 0 + 2$$$ и $$$2 \ne 0 + 1$$$;
  • префикс $$$[0, 1, 2, 1]$$$ является хорошим массивом, так как $$$2 = 0 + 1 + 1$$$;
  • префикс $$$[0, 1, 2, 1, 4]$$$ является хорошим массивом, так как $$$4 = 0 + 1 + 2 + 1$$$.

Как видно, три из них являются хорошими, поэтому ответ равен $$$3$$$.