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. ie, the distance between points (x₁,y₁) and (x₂,y₂) is given by sqrt((x₁-x₂)²+(y₁-y₂)²). 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 |x₁-x₂|+|y₁-y₂|

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<=x_i,y_i<=10⁸) 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