Wstęp do programowania w C++

Dwa po(d)ciągi

Jasiu jest manewrowym na kolei. Do jego obowiązków należy między innymi sprzęganie i rozprzęganie taboru. Od jakiegoś czasu na stacji manewrowej pojawia się pociąg ze specjalnym składem, nie jest to jednak złoty pociąg...
Skład ten złożony z wagonów należy rozdzielić na dwa składy tak, aby spełniony był pewien warunek. Jasiu nie dopytuje dlaczego tak, po prostu wykonuje swoją robotę. Warunkiem tym jest jednakowa suma oznaczeń wagonów w obu rozdzielonych składach. Czasem nie jest to możliwe, wówczas Jasiu musi przestawiać lub doczepiać inne wagony, tego chce jednak uniknąć, bo to sporo dodatkowej pracy. Czasem jednak taki podział możliwy jest na więcej niż jeden sposób, wówczas maszynowy już sam decyduje, gdzie nastąpi rozdzielenie składu. Twoim zadaniem jest pomóc Jasiowi i udzielić odpowiedzi, na ile sposobów może rozdzielić skład na dwa składy, aby spełniony był warunek. Inaczej mówiąc, na ile sposobów można ciąg liczb całkowitych podzielić na dwa spójne podciągi tak, aby sumy wyrazów obu podciągów były takie same?

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Dla każdego przypadku testowego w pierwszym wierszu znajduje się liczba całkowita n (2 ≤ n ≤ 10⁵) oznaczająca liczbę wagonów. W wierszu drugim znajduje się n liczb całkowitych a_i (-10⁶ ≤ a_i ≤ 10⁶) będących oznaczeniami kolejnych wagonów. Pliki wejścia nie przekraczają 2MB.

Wyjście
Dla każdego przypadku testowego należy odpowiedzieć na pytanie nurtujące Jasia.

Przykład

Wejście
2
3
1 2 3
4
-1 2 0 2

Wyjście
1
0