WCIPEG 2018 ECOO Qualifier
Kanade was not really satisfied with last year's scores on the problem "Shattering Shadows". Specifically, no one solved it! Thus, she decided to torture the students who failed it by giving them the exact same problem but in three dimensions.
There are shadows, represented by points, on a 3-dimensional coordinate plane. Kanade is located at the origin and can shoot an arrow in any direction. However, some shadows might be blocked by other shadows, which Kanade is not able to hit. Count how many shadows Kanade can shoot.
For 90% of cases, .
Input Specification
Line 1: , the number of test cases.
Each case consists of the following: An integer , the number of shadows.
lines, each with 3 integers , , , between to ,
representing one shadow. No shadow will be located at point (0, 0, 0)
.
Output Specification
For each case, output the number of shadows that can be hit on a separate line.
Sample Input
3
4
10 10 10
-5 -5 -5
0 0 -1
1 1 1
6
-1 0 0
1 0 0
0 -1 0
0 1 0
0 0 -1
0 0 1
3
1 1 1
1 1 1
1 1 1
Sample Output
3
6
1
Comments