Convex hull of the 3D - 2
n
points are given in the space. No 4 points lie in one plane. Find the convex hull of these points.
Input
The first line contains the number of test cases m
. The following lines describe the tests. Each test starts with a line containing n
(1 ≤ n ≤ 1000
) - number of points. Further, the n rows are given by three numbers - the coordinates of points. All coordinates are integers, do not exceed 500. The total number of points does not exceed 2100.
Output
For each test, the following output. In the first line of the output number of edges m
. Coming up next m
lines output description of the faces: the number of vertices and number of points in the original set. The points are numbered in the order in which they are given in the input file. Points within the faces must be sorted in order of counterclockwise relative to the outer normal to the face.