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 (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