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
2014-01-25 12:16:53 Abhinav Gupta
Lot of Google helped me :P
2014-01-24 14:11:23 Chandan Mittal
easy 1 :)
2013-11-23 18:40:02 Shanmukha Boora
@HWK can u please check my submission... getting WA ID:10527173

Last edit: 2013-11-23 19:05:01
2013-08-11 09:19:23 Raman Shukla
Nice problem... Enjoyed doing it...
2011-10-02 23:35:11 ZiYuan
@HWK, my fault. I forgot to put "\n"'s to the output.
2011-10-02 16:28:25 HWK
@ZiYuan: You didn't blunder. Only add whitespace to the output. ;-)
I changed the problem description to clarify this.

Last edit: 2011-10-02 16:28:56
2011-10-02 16:28:25 ZiYuan
@HWK, could you tell me the test case where I blundered? The submission ID is 5762600 or 5762625. Thank you~

Last edit: 2011-10-02 08:32:37
2011-10-02 16:28:25 npenate
@HWK
Thanks
2011-10-02 16:28:25 HWK
@Nelson González Peñate (UCI-01):
E.g.
5 75 19
79 94 66
35 79 38
87 53 97
64 84 40
=> 3, not 5.
2011-10-02 16:28:25 npenate
@HWK
ID: 5588789
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.