3Sum

2000ms    65536K
2    1
Easier

Description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

Input

There are multiple test cases.

The first line contain a positive integer N. means there are N test cases.

Following N lines, for each line start with an integer M followed by M integers (3<M<=10000). M means the size of array. 

Output

For each test case output the number of such triplets in a line.

Sample Input

1
6 -1 0 1 2 -1 -4

Sample Output

2

Hint

For {-1 0 1 2 -1 -4}  array there are 2 possible triplets:

(-1, 0, 1)

(-1, -1, 2)

 

Source

Editor

keefo on 2015-01-23 05:02:55


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC