CF2033D Kousuke's Assignment

After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array $ a $ of $ n $ integers and asked him to calculate the number of non-overlapping segments of the array $ a $ , such that each segment is considered beautiful. A segment $ [l,r] $ is considered beautiful if $ a_l + a_{l+1} + \dots + a_{r-1} + a_r=0 $ . For a fixed array $ a $ , your task is to compute the maximum number of non-overlapping beautiful segments.

The first line of input contains the number $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of $ 2 $ lines. - The first line contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array. - The second line contains $ n $ integers $ a_i $ ( $ -10^5 \le a_i \le 10^5 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 3\cdot 10^5 $ .

For each test case, output a single integer: the maximum number of non-overlapping beautiful segments.