TETRAHED - Point in tetrahedron

no tags 

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

hide comments
Abhinav Gupta: 2014-01-25 12:16:53

Lot of Google helped me :P

Chandan Mittal: 2014-01-24 14:11:23

easy 1 :)

Shanmukha Boora: 2013-11-23 18:40:02

@HWK can u please check my submission... getting WA ID:10527173

Last edit: 2013-11-23 19:05:01
Raman Shukla: 2013-08-11 09:19:23

Nice problem... Enjoyed doing it...

ZiYuan: 2011-10-02 23:35:11

@HWK, my fault. I forgot to put "\n"'s to the output.

HWK: 2011-10-02 16:28:25

@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
ZiYuan: 2011-10-02 16:28:25

@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
npenate: 2011-10-02 16:28:25

@HWK
Thanks

HWK: 2011-10-02 16:28:25

@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.

npenate: 2011-10-02 16:28:25

@HWK
ID: 5588789


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