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

Красота массива $$$v_1,v_2,\ldots,v_n$$$ равняется количеству индексов $$$i$$$ ($$$1 \le i \le n$$$), таких что $$$v_1+v_2+\ldots+v_i = 0$$$.

У вас есть массив $$$a_1,a_2,\ldots,a_n$$$ длины $$$n$$$. Вы можете применить к нему следующую операцию сколько угодно раз:

  • выбрать индекс $$$i$$$ ($$$1 \le i \le n$$$), такой что $$$a_i=0$$$;
  • после этого заменить $$$a_i$$$ на произвольное целое число.

Какой максимальной красоты массив $$$a$$$ вы можете получить?

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке даны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите одно число: максимальную красоту массива $$$a$$$ после применения к нему операций.

Пример
Входные данные
5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1
Выходные данные
3
1
4
4
5
Примечание

В первом наборе входных данных вы можете заменить $$$a_2$$$ на $$$-2$$$ за одну операцию. После этого массив $$$a$$$ станет равен $$$[2,-2,1,-1,0]$$$ и будет иметь красоту $$$3$$$:

  • $$$a_1+a_2=2-2=0$$$;
  • $$$a_1+a_2+a_3+a_4=2-2+1-1=0$$$;
  • $$$a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0$$$.

Во втором наборе входных данных вы можете заменить $$$a_3$$$ на $$$-2\,000\,000\,000$$$, чтобы получить массив красоты $$$1$$$.

В третьем наборе входных данных вы можете не делать операции.