Warmest thanks to Clive Fraser for creating this task!
A vast array of transmitters and receivers is spread over a large flat plain. A coordinate system (x,y) is used to map the plain. Each intersection of integer coordinates marks the position of a combined transmitter and receiver. All transmissions are carried out using very narrow beams of laser light. There is growing evidence that some of the transmissions are being intercepted by an enemy agent. This can only be achieved by modifying a receiver, after which any transmission which passes through the grid point of that receiver will be intercepted.
There is substantial security around the main transmitter/receiver at the origin (0,0), so no interception of transmissions can be taking place there. A safe block of transmitter receiver stations has also been established. These are situated in a straight line between positions (x1,y) and (x2,y) inclusive. There is a continual need to pass communications between the main station at the origin and stations within the safe block. However, a transmission between one of the stations in the safe block and the main station at the origin might pass through one or more other stations on the way. It is assumed that all other stations could potentially be configured to intercept the signal so we must use only those safe block stations which can send or receive a signal from the main station without it passing through any other station on the way. When the signal successfully reaches its destination it is removed so cannot continue to reach any further stations.
The problem is to find the number of stations within the safe block which can communicate with the main station without having the signal pass through any other stations between them. Consider a safe block with one end at (-3,4) and the other end at (6,4). There are 10 stations in the safe block but it is easy to verify that only 5 of them can transmit to the main station without the transmission passing through any other station on the way. These 5 stations are situated at the points: (-3,4), (-1,4), (1,4), (3,4) and (5,4).
The magnitudes of x1, x2 and y will always be less than 10^12.
Input/Output description: The first line of the input data will contain a single integer N, the number of puzzles. N lines will follow. Each of these contains three space-separated integers x1, x2 and y. For each puzzle, you need to determine the number of stations in the safe block which can transmit to the main block without passing through any other station. Give your answers as a single string, separated by spaces.
Example:
input:
5
-3 6 4
-84 27 -44
-905 219 -593
2821 7181 -1825
-86876 44169 -31273
answer:
5 51 1123 3441 119091