Jack Skellington kidnapped Sandy Claws so he can replace him on Christmas! The monsters of Halloween Town are helping Jack make toys for all the children.
One of these toys is a special kind of gyroscopic exercise tool. It consists of balls that levitate around the center of the toy. To play with it, a child chooses some axis passing through the center and begins to rotate all the balls around it simultaneously. The effort needed to perform the exercise is proportional to the sum of squared distances from every ball to the chosen axis. If the needed effort for this axis is not less than for any other one, we call it The Axis of Awesome. Now Jack wants to improve these gyroscopic toys by adding zero or more balls to each toy so that every possible axis of play was an Axis of Awesome.
You are given the blueprints for gyroscopic toys, where each toy is described as a set of three-dimensional coordinates denoting the locations of the toy's balls. For each toy, find the the minimum number of balls Jack must add so that any possible axis would be called Axis of Awesome. If no amount of additional balls makes this possible, print -1
instead.
Note: The center of each toy is always located at point .
Input Format
The first line contains an integer, , denoting the number of gyroscopic toys. The subsequent lines describe each toy in the following format:
- The first line contains an integer, , denoting the number of balls in the toy.
- Each of the subsequent lines contain space-separated integers describing the respective , , and coordinates of one of the toy's balls.
Constraints
- Different balls may have the same coordinates.
Output Format
For each toy, print a single integer on a new line denoting the minimum number of balls Jack must add to the toy so that the effort to play with it is always maximal; if this is not possible, print -1
instead.
Sample Input 0
2
1
0 0 0
2
1 0 0
0 1 0
Sample Output 0
0
1
Explanation 0
Jack wants to improve the following toys:
- For the first toy, you don't need to add any balls because the effort is always and doesn't depend on the chosen axis. Because we didn't need to add any balls, we print on a new line.
For the second toy, we can add a ball at point so that the total squared distance from the updated set of balls to any axis is equal to :
Because we only needed to add one ball, we print on a new line.