D. Задание Косукэ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После поездки с Сакурако Косукэ очень испугался, потому что забыл о своем задании по программированию. В этом задании учитель дал ему массив $$$a$$$ из $$$n$$$ целых чисел и попросил вычислить количество непересекающихся отрезков массива $$$a$$$, таких что каждый отрезок считается красивым.

Отрезок $$$[l,r]$$$ считается красивым, если $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r=0$$$.

Для фиксированного массива $$$a$$$ ваша задача состоит в том, чтобы вычислить максимальное количество непересекающихся красивых сегментов.

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

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

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массива.
  • Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^5 \le a_i \le 10^5$$$) — элементы массива $$$a$$$.

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

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

Для каждого теста выведите одно целое число: максимальное количество непересекающихся красивых отрезков.

Пример
Входные данные
3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1
Выходные данные
1
2
3