题目描述

格点是坐标均为整数的点，格点多边形是所有顶点均为格点的多边形。如果一个多边形内任意两点之间的线段都完全包含在该多边形内（或在其边界上），则称其为凸多边形。等价地说，凸多边形每个顶点处的内角均小于180度。

对于一组格点集合S，其凸包是包含所有这些点的最小凸（格点）多边形（凸包的顶点必须属于该格点集合）。如果所有点都位于同一条直线上，则凸包将退化为一条线段（退化多边形，见下图最右侧）。在下图中，集合中的点用实心点表示，凸包的顶点用X表示，凸包则通过连接这些顶点绘制而成。注意，凸包多边形上的点并非都是顶点。

凸包的顶点按以下标准顺序排列： a) 第一个顶点是y值最大的点。如果有多个顶点y值相同，则取x值较小的点作为第一个顶点。 b) 顶点按顺时针方向围绕多边形排列。

编写一个程序，读取一组格点，然后按标准顺序输出其凸包的顶点。

输入

输入的第一行包含一个整数P（1 ≤ P ≤ 1000），表示随后的数据组数。每组数据的第一行包含数据集编号，后跟一个空格，再后跟一个十进制整数N（3 ≤ N ≤ 50），表示该集合中的点数。数据集中的其余行包含集合中的点，每行最多5个点（最后一行可能少于5个）。每个点由两个用空格分隔的十进制整数值表示，分别代表x和y坐标。

输出

对于每组数据集，输出包含多行。第一行包含一个十进制整数，表示数据集编号，后跟一个空格，再后跟一个十进制整数，表示凸包的顶点总数。随后按标准顺序输出凸包的顶点，每行一个顶点，每行包含十进制整数x坐标、一个空格和十进制整数y坐标。

输入示例 1

4 
1 25 
2 1 7 1 1 2 9 2 1 3 
10 3 1 4 10 4 1 5 10 5 
2 6 10 6 2 7 9 7 3 8 
8 8 4 9 7 9 6 2 3 3 
5 4 7 5 8 6 4 6 3 7 
2 30 
3 9 6 9 3 8 9 8 3 7 
12 7 2 6 12 6 2 5 12 5 
2 4 12 4 1 3 11 3 1 2 
11 2 1 1 11 1 1 0 10 0 
4 -1 10 -1 7 -2 10 -2 5 0 
7 3 4 5 6 8 3 1 2 6 
3 3 
3 1 2 2 1 3 
4 6 
1 3 19 1 4 2 2 1 11 2 
10 1

输出示例 1

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