CRAN02 - Roommate Agreement


Leonard was always sickened by how Sheldon considered himself better than him. To decide once and for all who is better among them they decided to ask each other a puzzle. Sheldon pointed out that according to Roommate Agreement Sheldon will ask first. Leonard seeing an opportunity decided that the winner will get to rewrite the Roommate Agreement.

Sheldon thought for a moment then agreed to the terms thinking that Leonard will never be able to answer right. For Leonard, Sheldon thought of a puzzle which is as follows. He gave Leonard n numbers, which can be both positive and negative. Leonard had to find the number of continuous sequence of numbers such that their sum is zero.

For example if the sequence is- 5, 2, -2, 5, -5, 9

There are 3 such sequences

2, -2

5, -5

2, -2, 5, -5

Since this is a golden opportunity for Leonard to rewrite the Roommate Agreement and get rid of Sheldon's ridiculous clauses, he can't afford to lose. So he turns to you for help. Don't let him down.

Input

First line contains T - number of test cases

Second line contains n - the number of elements in a particular test case.

Next line contain n elements, aiĀ (1 <= i <= n) separated by spaces.

Output

The number of such sequences whose sum if zero.

Constraints

1 <= t <= 5

1 <= n <= 10^6

-10 <= ai <= 10

Example

Input:
2
4
0 1 -1 0
6
5 2 -2 5 -5 9

Output:
6
3

hide comments
anuragdw0710: 2021-08-27 13:56:55

I thought two pointer will be bruteforce approch

jinx_11: 2021-06-21 17:40:56

I also cracked it using hashing and prefix sum but not able to formulate a two-pointer method...ugh!!

fardin_abir: 2020-04-18 06:36:39

prefix sum + map is the simplest way...

yaseenmollik: 2018-12-20 02:50:25

Finally solved it using prefix sum and hashing :D

youknowwho37: 2018-03-20 04:10:41

How to solve this by using 2pointers?

doaa_ismael_9: 2017-08-13 10:39:34

Is there any one who solve it with two pointers technique??
I can't solve it , help me please :(

Sachin verma: 2017-08-10 15:19:55

Trailing spaces in input. Got WA in python because of that.

vaibhavk31: 2017-07-08 13:55:23

Declare long long !!
it caused me 1WA :)

jai1998: 2017-07-05 14:49:17

Prefix Sum and Hashmap. Easy :)
My 150th

sandeep_4141: 2017-06-12 08:45:30

use sum array to store prefix sum ,and count the frequency .


Added by:CSI
Date:2013-02-16
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64