406356: GYM102388 B Stars

On Planet E, there are many stars!

To be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($$$(x, y)$$$ where both $$$x$$$ and $$$y$$$ are integers).

People on Planet E have a hobby of drawing straight segments between the stars. One day, they are curious about how many stars their straight segments have covered.

Can you help the people on Planet E to count the number of stars on their straight segments?

The first line contains a positive integer $$$T$$$ ($$$T \le 100$$$), the number of testcases.

Each testcase contains 4 integers $$$x_0, y_0, x_1, y_1$$$ ($$$|x_i| \le 10^9$$$ and $$$|y_i| \le 10^9$$$ for $$$i = 0, 1$$$), representing the segment $$$(x_0, y_0)$$$ to $$$(x_1, y_1)$$$.

For each testcase, output a single line consisting of the number of stars on the segment.

4
1 1 1 1
1 2 3 6
-1 -1 50 101
-10000 1 1000000000 0

1
3
52
2

In the first testcase, the only covered star is $$$(1, 1)$$$.

In the second testcase, the covered stars are $$$(1, 2), (2, 4), (3, 6)$$$.