D :: Rescue Beacon

Time Limit: 2 Seconds Memory Limit: 65536 KB

While attempting to evade some old and not-so-happy creditors of his, Han Solo crashed the Millennium Falcon on the ice-world of Hoth. Now he must get some sort of emergency signal working so that he can get rescued before his Wookiee friend becomes a fur-cicle or decides to eat a Hans-kabob. Can you help him?

Han managed to salvage a really bright laser that can be seen from light-years away, and thought that would make a good signal. The downside is that if he just shines it straight up into the sky, there would only be a minimal chance that someone happens to be in the path of the light to see it. Chewbacca, in the meantime, was playing with a bunch of highly-reflective, multi-faceted crystals he found in a cave nearby. Then, in a moment of inspiration, Han realized he could assemble a rescue beacon by shining the light down on the crystal, whose facets will in turn reflect the light into the sky in a multitude of directions!

Figure 1: A simplified, two-dimensional illustration of Han's rescue beacon.

The only problem that remains is in deciding which crystal to use as the light reflector. Each of the reflective crystals is a convex polyhedral shape whose surface consists solely of perfectly triangular facets, and can be fitted in the beacon in any orientation. Of course, the best crystal to use is the one that would reflect the laser beam (which consists of parallel light rays from a single direction) back in the greatest number of directions. In other words, you can think of the reflective merit of a crystal as simply the number of facets on it that you can see from any one viewing direction, as those are the facets that can be hit simultaneously by the laser beam. Given a description of the geometry of each of the crystals, can you compute the greatest number of directions the crystal can reflect the laser?

Input

The input will consist of geometric descriptions of the crystals in Chewbacca's collection. The description of each crystal begins with an integer n (4 ≤ n ≤ 2000), the number of facets on the crystal, on a single line followed by n lines describing the facets. Each facet is described by 9 integers, x1 y1 z1 x2 y2 z2 x3 y3 z3, where the points (x1, y1, z1), (x2, y2, z2), and (x3, y3, z3) in three dimensions form the vertices of the triangular facet in counter-clockwise order (on a right-handed coordinate frame) as viewed from the exterior. All coordinates are in the range -2000 ≤ xi, yi, zi ≤ 2000, no single facet has a surface area greater than 200,000, and no two facets face the same direction. You can expect that when all facets of each crystal are assembled, they form a closed convex polyhedron. Lastly, no crystal will have a structure with any degeneracy that would cause ambiguity as to how many facets the laser can hit. In other words, it should not matter whether you consider facets parallel to the laser beam as capable of reflecting the beam or not -- the test data have been constructed such that either interpretation would yield the same answer. In other words, it should not matter whether you consider facets parallel to the laser beam as capable of reflecting the light or not. Input is terminated by a line containing the number 0 (do not process this as a test case).

Output

For each crystal, output on a single line containing an integer m: the greatest number of directions that the crystal can simultaneously reflect the laser beam.

Sample Input

4 
0 1 1 -2 0 0 2 0 0 
0 1 1 2 0 0 0 3 0 
0 1 1 0 3 0 -2 0 0 
-2 0 0 0 3 0 2 0 0 
6 
0 1 1 -2 0 0 2 0 0 
0 1 1 2 0 0 0 3 0 
0 1 1 0 3 0 -2 0 0 
-2 0 0 0 1 -1 2 0 0 
2 0 0 0 1 -1 0 3 0 
0 3 0 0 1 -1 -2 0 0 
0

Sample Output

3 
4

Submit