HEROARR - Heroes Arrangement

Please click here to download a PDF version of the contest problems. The problem is problem H in the PDF.


There are N heroes in the Kingdom of Heroes, each hero has a special range of activity, this "range" is a delta-shaped region (triangle region including the boundary; it is guaranteed that all triangles will neither degenerate into a segment nor a point using the King’s angle of view), and heroes can appear in any point in his activity range. The king, standing at the Origin (0, 0, 0), is observing the heroes. No range of activity will contain the king’s position.

You may assume that no hero could meet others, that means these "range" have no common point. Your task is to find number K, indicating that the king can choose at most K heroes such that no pairs of chosen heroes cause one may block the king’s view line to observe another. In other words, no hero can appear on the segment between another hero and the King.

Input

There are multiple test cases, the number of them, T, is given in the very first line of the input, followed by T cases.

For each test case:

First line contains an integer N, the number of heroes, 1 ≤ N ≤ 40. Then N lines follow, each line contains nine integers x1 y1 z1 x2 y2 z2 x3 y3 z3, denoting the coordinates of the delta-shaped regions’ vertex respectively, -100 ≤ x1, y1, z1, x2, y2, z2, x3, y3, z3 ≤ 100.

Output

Output a single line with a number K with case number, the maximum number of heroes king can choose.

Example

Input:
2
2
0 0 1 1 2 1 -1 2 1
0 0 2 1 -2 2 -1 -2 2
2
0 0 1 1 2 1 -1 2 1
0 0 -1 1 -2 -1 -1 -2 -1

Output:
Case #1: 1
Case #2: 2

Hint

The sample image of the sample input is drawn below, the small sphere is the position of the king.

Heroes Arrangement

Added by:Fudan University Problem Setters
Date:2009-11-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET
Resource:ACM/ICPC Regional Contest, Shanghai 2009

hide comments
2023-02-04 15:24:02 Simes
I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.