TETRAHED - Point in tetrahedron

There're given 5 points in 3D coordinates (integers 0 <= x, y, z < 100). Their order is arbitrary. 4 of them are the vertices of a tetrahedron whose edges can be of different size. One is lying in this tetrahedron. Find its index (1-5) in the array of points.

Input

In the first line the number T (T<1000) of test cases.
Then for each test case 5 lines with the space separated x-, y- and z-coordinates of the 5 points.

Output

For each test case a line with the index of that point which is lying in the tetrahedron formed of the 4 other points.

Example

Input:
1
5 72 66
92 23 68
60 60 49
74 78 33
67 76 27 Output: 3

Added by:HWK
Date:2011-08-07
Time limit:1.944s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-10-02 16:28:25 HWK
@Nelson González Peñate (UCI-01): Which ID?
2011-10-02 16:28:25 npenate
@HWK
I got AC but:
Could you help me to understand why when I try to find the point where the sum of the distances to the other points is the smallest possible, I get WA?

Last edit: 2011-09-04 18:23:34
2011-10-02 16:28:25 Pranay
@HWK: Thanks :)
2011-10-02 16:28:25 HWK
@Pranay: e.g.
0 42 79
6 48 59
8 49 60
24 73 16
71 20 60
=> 3 not 5
2011-10-02 16:28:25 HWK
@pizza boy: If it is too easy for you try it to shorten: http://www.spoj.pl/SHORTEN/problems/TETRAHE1/
2011-10-02 16:28:25 যোবায়ের
thanks, I solved that assuming those. although easy, nice problem :)
2011-10-02 16:28:25 HWK
They are unique and the fifth point lies strictly inside.
2011-10-02 16:28:25 যোবায়ের
are the points unique? and will the target point lie strictly inside?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.