There are $n$ stars on a drawing board, which can be viewed as points in a two-dimensional plane. The $i$-th star ($1 \le i \le n$) has coordinates $(x_i, y_i)$. It is known that all stars have distinct $x$-coordinates and distinct $y$-coordinates.

Each time you draw a constellation, you need to select three stars from these $n$ stars and connect them to form a triangle. To reflect a sense of balance, this triangle must satisfy a specific boundary requirement: there exists a rectangle with all four sides parallel to the coordinate axes such that the three vertices of the triangle lie exactly on the boundary of this rectangle. At the same time, to maintain a clear structure of the star map, the interior regions (excluding vertices and boundaries) of all drawn triangles must be pairwise disjoint.

Please calculate the maximum number of constellations that can be successfully drawn and provide a specific drawing scheme.

Input

Each test point contains multiple test cases. The first line contains a positive integer $T$ ($1 \le T \le 2 \times 10^4$), representing the number of test cases. For each test case:

• The first line contains a positive integer $n$ ($3 \le n \le 2 \times 10^5$), representing the number of stars.
• The next $n$ lines each contain two integers $x_i, y_i$ ($|x_i|, |y_i| \le 10^9$), representing the coordinates of the $i$-th star. It is guaranteed that all $x_i$ are distinct and all $y_i$ are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case:

• The first line outputs a non-negative integer $m$, representing the maximum number of constellations that can be drawn.
• The next $m$ lines each output three distinct positive integers $x, y, z$ ($1 \le x, y, z \le n$), representing the three stars that form a constellation.

Examples

Input 1

2
8
-10 1
-2 6
5 10
8 -9
-1 -2
3 0
0 3
1 -8
8
8 8
-5 3
-4 1
5 7
10 10
-3 5
-8 -10
-7 -1

Output 1

8
6 5 8
6 8 4
1 6 5
7 1 6
2 7 1
3 2 7
3 7 6
3 6 4
2
2 3 8
6 2 3

Note

For the first test case, the star map drawn in the sample output is shown below:

For the second test case, the star map drawn in the sample output is shown below: