Aloknath is obsessed with kanyadaan. So much that he decides to do kanyadaan on n girls in a single day.

Babuji believes that a continuous series of kanyadaan (of any length) is magical if age of all the girls in those kanyadaan's is equal. Babuji wants to find out the number of magical kanyadaan that he will do in a day.

Can you do this task for babuji ?

Note : Length of series >=1

Input

The first line contains number of test cases t(t<=10)

For each test case the first line of the input data contains an integer n (1â‰¤nâ‰¤10^5).

and the second line contains n integers a1,a2,...,an (0â‰¤aiâ‰¤10^9) denoting the ages of girls.

Output

For each test case print on the single line print the number of magical kanyaddan that babuji will do.

Sample test(s)

input

2

4

2 1 1 4

5

2 2 2 0 1

output

5

8