После поездки с Сакурако Косукэ очень испугался, потому что забыл о своем задании по программированию. В этом задании учитель дал ему массив \(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\) по всем наборам входных данных не превышает \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач