H

Lattice Point or Not

Input: Standard Input

Output: Standard Output

 

Now a days a very common problem is: “The coordinate of two points in Cartesian coordinate system is (200, 300) and (4000, 5000). If these two points are connected we get a line segment. How many lattice points are there on this line segment.” You will have to do a similar task in this problem – the only difference is that the terminal coordinates can be fractions.

 

Input

First line of the input file contains a positive integer N (N<=50000) that denotes how many lines of inputs follow. This line is followed by N lines each of which contains four floating-point numbers x1, y1, x2, y2 (0< |x1|, |y1|, |x2|, |y2| <=200000). These floating-point numbers has exactly one digit after the decimal point.

 

Output

For each line of input except the first line produce one line of output. This line contains an integer which denotes how many lattice points are there on the line segment that connects the two points (x1, y1) and (x2, y2).

 

Sample Input                               Output for Sample Input

3

10.1 10.1 11.2 11.2

10.2 100.3 300.3 11.1

1.0 1.0 2.0 2.0

1

0

2

 

Problemsetter: Shahriar Manzoor

Special Thanks: Derek Kisman