TRIEQUAL - Triangle equality

no tags 

Consider three distinct points A,B,C on a plane. The sum of straight line distances from A to B and B to C is always greater than or equal to the straight line distance from A to C. Equality holds only when ABC is a degenerate triangle. This is the famous triangle inequality.

In this case, distance between points is measured by the Euclidean metric, i.e. the distance between points (x1, y1) and (x2, y2) is given by sqrt((x1 - x2)2 + (y1 - y2)2). However, this is not the only metric possible. Another common metric used is the Manhattan metric where the distance between the pair of points is given by |x1 - x2| + |y1 - y2|.

You are given N distinct points on a plane where distances are measured using the Manhattan metric. Find the number of ordered triplets of distinct points (A, B, C) such that the sum of distances from A to B and B to C is equal to the distance from A to C.

Input

The first line of input contains an integer T (≤ 10), the number of test cases to follow.

Following this are the descriptions of T test cases. Each test case description begins with an integer N (≤ 50000), the number of points. Following this are N lines, each giving the x and y coordinates of a point (0 ≤ xi, yi ≤ 108) separated by a space.

Output

Output T lines, each containing the number of ordered triplets of distinct points in every test case with the given property

Example

Input:
2
3
0 0
1 1
2 2
3
0 0
1 2
2 1

Output:
2
0


Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011