Різні суми#12916

Різні суми

1 секунда
256 мегабайтів
Середня

Дано масив цілих чисел довжиною . Ви хочете розбити його на найбільшу можливу кількість послідовних підмасивів, так щоб виконувалася наступна умова:

На яку найбільшу кількість підмасивів ви можете розбити масив за такої умови?

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^5)  — кількість тестових наборів. Далі йде опис кожного тестового випадку.

Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 2\cdot 10^5)  — довжину масиву.

Другий рядок кожного тестового набору містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9)  — елементи масиву.

Вихідні дані

Для кожного тестового набору виведіть одне ціле число  — відповідь на задачу.

Приклади

Приклад

Loading
Loading

Примітка

У першому тестовому наборі ми можемо розбити [1, 2, 3, 4] на підмасиви [1], [2], [3], [4]. Суми в цих підмасивах дорівнюють 1, 2, 3, 4, жодні дві сусідні суми не рівні.

У другому тестовому наборі ми можемо розбити [1, 1, 1, 1] на підмасиви [1], [1, 1, 1], [1]. Суми в цих підмасивах дорівнюють , жодні дві сусідні суми не рівні.

У третьому тестовому наборі ми можемо розбити [2, 1, 1, 1, 1, 2] на підмасивів [2], [1], [1, 1], [1], [2]. Суми в цих підмасивах дорівнюють 2, 1, 2, 1, 2, жодні дві сусідні суми не рівні.