Дано масив цілих чисел довжиною . Ви хочете розбити його на найбільшу можливу кількість послідовних підмасивів, так щоб виконувалася наступна умова:
Нехай — кількість підмасивів, а s_1, s_2, \ldots, s_k — суми елементів у відповідних підмасивах. Тоді s_i \neq s_{i+1} для всіх 1 \leq i \leq k-1. (Зверніть увагу, що вам не потрібно, щоб всі сум були попарно різними, вам потрібно лише, щоб сусідні суми були різними).
На яку найбільшу кількість підмасивів ви можете розбити масив за такої умови?
Перший рядок містить одне ціле число (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) — елементи масиву.
Для кожного тестового набору виведіть одне ціле число — відповідь на задачу.
Приклад
У першому тестовому наборі ми можемо розбити [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, жодні дві сусідні суми не рівні.