favorite We need a little bit of your help to keep things running, click on this banner to learn more



You are given a set of points in 3-D space. Your task is to calculate the number of k vertex sides of the convex polyhedron with minimal volume that contains the whole given set of points.


First line of input contains the quantity of tests T (1T100). First line of each test case contains the number of points in given set N (4N30). Then N lines follow, each of which contains 3 integer numbers: X, Y, Z (–1000X, Y, Z1000) – coordinates of points. Some points can have the same coordinates! It’s guaranteed, that any convex polyhedron, that contains all given points, has a positive volume.


For each of T test cases output a line of the form "Case #A:", where A is the number of test (beginning from 1), and then – M more lines, where M is the quantity of different side types (a side type means quantity of its vertices). In each of the next M lines you have to output two numbers: k – the number of vertices in the side and qk – the number of k vertex sides in the polyhedron. After k you must print a colon ":" and then – a space. You have to output the result in ascending order of k. The quantity of vertices in a side is determined only by geometrical meanings. That is, if a given point lies on an edge of a side, it mustn’t be considered as a vertex, and if some such point lie in one vertex, they must be considered as a single vertex.

Time limit 5 seconds
Memory limit 64 MiB
Input example #1
0 0 0
2 0 0
0 2 0
2 2 0
3 1 0
1 1 1
0 0 0
1 1 0
0 2 0
2 1 0
1 1 1
Output example #1
Case #1:
3: 5
5: 1
Case #2:
3: 4