Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) AxBxCxD are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2²⁸ ) that belong respectively to A, B, C and D .

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

1

6

-45 22 42 -16

-41 -27 56 30

-36 53 -37 77

-36 30 -75 -46

26 -38 -10 62

-32 -54 -6 45

Sample Output

5

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <list>

 #include <iomanip>

 #include <cstdlib>

 #include <sstream>

 using namespace std;

 typedef long long LL;

 const int INF=0x5fffffff;

 const double EXP=1e-;

 const int MS=;

 int A[MS],B[MS],C[MS],D[MS],n,sum[MS*MS];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)

             scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);

         int cnt=;

         for(int i=;i<n;i++)

             for(int j=;j<n;j++)

                 sum[cnt++]=A[i]+B[j];

         sort(sum,sum+cnt);

         LL ans=;

         for(int i=;i<n;i++)

             for(int j=;j<n;j++)

         {

             ans+=upper_bound(sum,sum+cnt,-C[i]-D[j])-lower_bound(sum,sum+cnt,-C[i]-D[j]);

         }

         printf("%lld\n",ans);

         if(T)

             printf("\n");

     }

     return ;

 }