Famous wizard Sumar moonji kumaru is stuck in a huge room and has to save Hermione Granger from a monster. Kumaru is at location P1 given by integral coordinates (x_{1},y_{1}) and Hermione is at location P2 given by integral coordinates (x_{2},y_{2}). 
Sadly P1 and P2 are the only points at which floating rocks are present. Rest of the room is without floor and underneath is hot lava. 

Kumaru has to go from P1 to P2 but there are no floating rocks to walk on. Kumaru knows a spell that can make the rocks appear but only on the integral coordinates on the straight line joining P1 and P2.

How many rocks can appear at locations (x,y) on the line segment between P1 and P2 (excluding P1 and P2) which satisfy the condition that both x and y are integers?

Input Format 

The first line contains a single integer T, the number of test cases. T lines follow. 

 Each of the following T lines contains one test case each. Each test case contains 4 integers x_{1}, y_{1}, x_{2} and y_{2} separated by a single space. 

Output Format 

A single line containing the number of rocks.

Constraints 

1 <= T <= 10^{5} 

-10^{9} <= x_{1}, y_{1}, x_{2}, y_{2} <= 10^{9}

Sample input  

3
0 2 4 0
2 2 5 5
1 9 8 16

Sample Output

1
2
6

Explanation   

Case 1: As shown in the figure, between (0,2) and (4,0) there's only 1 integral point (2,1) hence 1 rock. 

Case 2: Between (2,2) and (5,5) lies (3,3) and (4,4), hence 2 rocks. 

Case 3: Between (1,9) and (8,16) there lies 6 rocks at positions (2,10) (3,11) (4,12) (5,13) (6,14) (7,15).

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


from fractions import gcd
n = int(input())
for i in range(n):
	h = [int(j) for j in input().split(' ')]
	if h[0] > h[2]:
		(a, b, c, d) = (h[2], h[3], h[0], h[1])
	elif h[0] < h[2]:
		(a, b, c, d) = (h[0], h[1], h[2], h[3])
	elif h[1] > h[3]:
		(a, b, c, d) = (h[2], h[3], h[0], h[1])
	elif h[1] < h[3]:
		(a, b, c, d) = (h[0], h[1], h[2], h[3])
	else:
		print(0)
		continue
	(e, f) = (d - b, a - c)
	m = gcd(e, f)
	e = e // m
	f = f // m
	count = 0
	if f <= 0:
		while a < c or b < d:
			a += f
			b += e
			count += 1
	else:
		while a < c or b < d:
			a += f
			b -= e
			count += 1
	print(count - 1)


from fractions import gcd
n = int(input(''))
data = [0] * 4
for i in range(n):
	data = [int(input_) for input_ in input('').split(' ')]
	print(gcd(abs(data[1] - data[3]), abs(data[0] - data[2])) - 1)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def CountPoints(x1, y1, x2, y2):
	p1 = abs(x2 - x1)
	q1 = abs(y2 - y1)
	g = gcd(p1, q1)
	return g - 1
T = int(input())
while T:
	T = T - 1
	(x1, y1, x2, y2) = input().split()
	x1 = int(x1)
	y1 = int(y1)
	x2 = int(x2)
	y2 = int(y2)
	print(CountPoints(x1, y1, x2, y2))


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	(x1, y1, x2, y2) = (int(_) for _ in input().split())
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


import fractions, math
t = int(input())
while t:
	t -= 1
	(x1, y1, x2, y2) = [int(x) for x in input().split()]
	X = x2 - x1
	Y = y2 - y1
	if X == 0:
		print(abs(y2 - y1) - 1)
		continue
	X = X // abs(fractions.gcd(X, Y))
	X = abs(X)
	if x1 > x2:
		x1 = x1 ^ x2
		x2 = x1 ^ x2
		x1 = x1 ^ x2
	x1 = (x1 // X + 1) * X
	x2 = (x2 // X - 1) * X
	print((x2 - x1) // X + 1)


from fractions import *
for _ in range(int(input())):
	(x1, y1, x2, y2) = [int(i) for i in input().split()]
	m = abs(y2 - y1)
	n = abs(x2 - x1)
	print(gcd(m, n) - 1)


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
sum = 0
for x in range(0, n):
	line = input().split()
	x1 = int(line[0])
	y1 = int(line[1])
	x2 = int(line[2])
	y2 = int(line[3])
	result = gcd(abs(x2 - x1), abs(y2 - y1)) - 1
	print(result)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for _ in range(T):
	(x1, y1, x2, y2) = [int(i) for i in input().split()]
	v = (abs(x2 - x1), abs(y2 - y1))
	print(gcd(v[0], v[1]) - 1)


c = int(input())

def coord(string):
	nros = string.split(' ')
	x = int(nros[0])
	y = int(nros[1])
	i = int(nros[2])
	j = int(nros[3])
	return (x, y, i, j)

def euclides(i, j):
	x = max(i, j)
	y = min(i, j)
	while y != 0:
		r = x % y
		x = y
		y = r
	return x

def rocas(string):
	xp = []
	yp = []
	(x1, y1, x2, y2) = coord(string)
	x3 = abs(x1 - x2)
	y3 = abs(y1 - y2)
	if min(x3, y3) == 0:
		return max(x3, y3) - 1
	piedras = euclides(x3, y3) - 1
	return piedras
for x in range(c):
	print(rocas(input()))


def gcd(m, n):
	while n > 0:
		r = m % n
		m = n
		n = r
	return m
T = int(input().strip())
for case in range(T):
	a = [0, 0]
	b = [0, 0]
	(a[0], a[1], b[0], b[1]) = map(int, input().strip().split())
	print(gcd(abs(b[1] - a[1]), abs(b[0] - a[0])) - 1)


import functools
from fractions import gcd
s = int(input())
order = []
for i in range(s):
	(x1, y1, x2, y2) = map(int, input().split(' '))
	a = abs(x1 - x2)
	b = abs(y1 - y2)
	y = functools.reduce(gcd, [a, b])
	order.append(y - 1)
for i in order:
	print(i)


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


import fractions
t = int(input())
while t > 0:
	t -= 1
	(x1, y1, x2, y2) = list(map(int, input().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
while t > 0:
	t -= 1
	l = list(map(int, input().split()))
	x1 = l[0]
	y1 = l[1]
	x2 = l[2]
	y2 = l[3]
	q = max(y1, y2)
	s = min(y1, y2)
	y = q - s - 1
	if x2 - x1 == 0:
		print(y)
		continue
	g = gcd(abs(y2 - y1), abs(x2 - x1)) - 1
	print(g)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return abs(a)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(x2 - x1, y2 - y1) - 1)


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, sys.stdin.readline().split()))
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = input().split()
	(x1, y1, x2, y2) = (int(x1), int(y1), int(x2), int(y2))
	dx = abs(x1 - x2)
	dy = abs(y1 - y2)
	g = gcd(dx, dy)
	print(g - 1)


def GCD(a, b):
	return GCD(b, a % b) if b else a
t = int(input())
for _ in range(t):
	(a, b, x, y) = list(map(int, input().split()))
	x -= a
	y -= b
	x = abs(x)
	y = abs(y)
	g = GCD(x, y)
	print(g - 1)


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	for i in range(int(input())):
		(x1, y1, x2, y2) = input().split()
		(x1, y1, x2, y2) = (int(x1), int(y1), int(x2), int(y2))
		(a, b) = (math.fabs(x1 - x2), math.fabs(y1 - y2))
		print(int(gcd(a, b)) - 1)
main()


from fractions import gcd

def main():
	for _ in range(int(input())):
		(x1, y1, x2, y2) = map(int, input().split())
		print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)
main()


def hcf(a, b):
	while b % a != 0:
		(a, b) = (b % a, a)
	return a
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = [int(j) for j in input().split()]
	if x1 == x2:
		print(abs(y2 - y1) - 1)
		continue
	if y1 == y2:
		print(abs(x2 - x1) - 1)
		continue
	if abs(x2 - x1) < abs(y2 - y1):
		delta_y = abs(y1 - y2)
		delta_x = abs(x1 - x2)
		rem = delta_y % delta_x
		if rem == 0:
			print(delta_x - 1)
			continue
		gcd = hcf(rem, delta_x)
		mul = delta_x // gcd
		count = delta_x // mul
		if delta_x % mul == 0 and count > 0:
			count -= 1
		print(count)
	else:
		delta_y = abs(y1 - y2)
		delta_x = abs(x1 - x2)
		rem = delta_x % delta_y
		if rem == 0:
			print(delta_y - 1)
			continue
		gcd = hcf(rem, delta_y)
		mul = delta_y // gcd
		count = delta_y // mul
		if delta_y % mul == 0 and count > 0:
			count -= 1
		print(count)


from fractions import gcd
t = int(input())
for _ in range(t):
	A = [int(x) for x in input().split()]
	print(gcd(abs(A[2] - A[0]), abs(A[3] - A[1])) - 1)


def gcm(m, n):
	if m == n:
		return m
	if m > n:
		x = m % n
		if x == 0:
			return n
		elif x == 1:
			return 1
		else:
			return gcm(n, x)
	else:
		return gcm(n, m)
T = int(input())
for x in range(T):
	l = list(map(lambda x: int(x), input().split()))
	(x1, y1) = (l[0], l[1])
	(x2, y2) = (l[2], l[3])
	dx = abs(x1 - x2)
	dy = abs(y1 - y2)
	if dx == 0:
		print(dy - 1)
		continue
	if dy == 0:
		print(dx - 1)
		continue
	g = gcm(dx, dy)
	f = dx // g
	print(dx // f - 1)


from fractions import gcd
t = int(input())
while t:
	t = t - 1
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x1 - x2), abs(y1 - y2)) - 1)


from fractions import gcd
t = int(input())
for i in range(t):
	s = input().split()
	dx = abs(int(s[0]) - int(s[2]))
	dy = abs(int(s[1]) - int(s[3]))
	print(gcd(dx, dy) - 1)


from fractions import gcd
t = int(input())
for case in range(t):
	(x1, y1, x2, y2) = tuple(map(int, input().split()))
	a = abs(y1 - y2)
	b = abs(x2 - x1)
	print(gcd(a, b) - 1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = [int(ns) for ns in str(input()).split()]
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	if dx:
		if dy:
			print(gcd(dx, dy) - 1)
		else:
			print(dx - 1)
	elif dy:
		print(dy - 1)
	else:
		print(0)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n_tests = int(input())
for t in range(n_tests):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from fractions import gcd
from math import floor
for _ in range(int(input())):
	(a, b, x, y) = [int(x) for x in input().split()]
	if a == x:
		c = b
		b = a
		a = c
		c = y
		y = x
		x = c
	m = (x - a) // gcd(x - a, y - b)
	print(floor(abs((x - a) / m) - 1))


from fractions import Fraction
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	if x1 == x2:
		print(abs(y1 - y2) - 1)
	elif y1 == y2:
		print(abs(x1 - x2) - 1)
	else:
		tg = Fraction(y1 - y2, x1 - x2)
		print(abs(x1 - x2) // tg.denominator - 1)


import fractions
for i in range(int(input())):
	(x1, y1, x2, y2) = input().split()
	dx = abs(int(x2) - int(x1))
	dy = abs(int(y2) - int(y1))
	if dx == 0:
		print(dy - 1)
	elif dy == 0:
		print(dx - 1)
	else:
		print(fractions.gcd(dx, dy) - 1)


n = int(input())
import fractions as f
for i in range(n):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	dx = abs(x1 - x2)
	dy = abs(y2 - y1)
	print(f.gcd(dx, dy) - 1)


import fractions
t = int(input())
for i in range(t):
	a = input().split()
	x1 = int(a[0])
	y1 = int(a[1])
	x2 = int(a[2])
	y2 = int(a[3])
	print(fractions.gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from math import ceil
from fractions import gcd
T = int(input().strip())
for t in range(T):
	(x1, y1, x2, y2) = [int(x) for x in input().strip().split(' ')]
	(x1, x2) = (min(x1, x2), max(x1, x2))
	(y1, y2) = (min(y1, y2), max(y1, y2))
	if y1 == y2:
		cnt = x2 - x1 - 1
	elif x1 == x2:
		cnt = y2 - y1 - 1
	else:
		m = (y2 - y1) / (x2 - x1)
		if m == int(m):
			cnt = x2 - x1 - 1
		else:
			d = gcd(y2 - y1, x2 - x1)
			cnt = d - 1
	print(max(cnt, 0))


from fractions import gcd
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = [int(x) for x in input().split()]
	m = x2 - x1
	n = y2 - y1
	m = abs(int(m))
	n = abs(int(n))
	g = gcd(abs(m), abs(n))
	q = n / g
	r = m / g
	count = 0
	if r == 0:
		count = max(y1, y2) - min(y1, y2) + 1
	elif q == 0:
		count = max(x1, x2) - min(x1, x2) + 1
	else:
		count += m // r + 1
		count = int(count)
	count -= 2
	print(count)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(p1_x, p1_y, p2_x, p2_y) = map(int, input().split())
	(x, y) = (abs(p1_x - p2_x), abs(p1_y - p2_y))
	print(gcd(x, y) - 1)


def get_number_of_int_coordinates(x1, y1, x2, y2):
	(dx, dy) = (abs(x2 - x1), abs(y2 - y1))
	if dx == dy == 0:
		return 0
	elif dx == 0:
		return dy - 1
	elif dy == 0:
		return dx - 1
	gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
	return gcd(dx, dy) - 1
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = [int(n) for n in input().split()]
	print(get_number_of_int_coordinates(x1, y1, x2, y2))


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from fractions import gcd
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = [int(x) for x in input().split()]
	print(abs(gcd(x1 - x2, y1 - y2)) - 1)


t = int(input())

def mod(x):
	if x < 0:
		x = -x
	return x

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for k in range(t):
	(x1, y1, x2, y2) = input().split(' ')
	x1 = int(x1)
	y1 = int(y1)
	x2 = int(x2)
	y2 = int(y2)
	c = 0
	g = abs(gcd(x2 - x1, y2 - y1))
	print(g - 1)


def gcd(a, b):
	if a:
		return gcd(b % a, a)
	return b
for xx in range(int(input())):
	(a, b, x, y) = map(int, input().split())
	a = abs(a - x)
	b = abs(b - y)
	print(gcd(a, b) - 1)


n = int(input())
for i in range(n):
	(x1, y1, x2, y2) = map(int, input().split())
	A = abs(y2 - y1)
	B = abs(x2 - x1)
	if not A:
		print(B - 1)
		continue
	elif not B:
		print(A - 1)
		continue
	(a, b) = (A, B)
	while b:
		(a, b) = (b, a % b)
	nzv = B // a
	print(B // nzv - 1)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	print(gcd(abs(y2 - y1), abs(x2 - x1)) - 1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input().strip())
for _ in range(t):
	(x1, y1, x2, y2) = [int(i) for i in input().strip().split()]
	print(abs(gcd(x2 - x1, y2 - y1)) - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = [int(_) for _ in input().split(' ')]
	v = (abs(x2 - x1), abs(y2 - y1))
	print(gcd(v[0], v[1]) - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = tuple(map(int, input().split()))
	print(abs(gcd(x2 - x1, y2 - y1)) - 1)


from math import sqrt

def gcd(a, b):
	while True:
		if a > b:
			r = a % b
			a = r
		else:
			r = b % a
			b = r
		if r == 0:
			return a * (a != 0) + b * (b != 0)
		if a < 0 or b < 0:
			return 1

def line_len(x1, y1, x2, y2):
	return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def g(x1, y1, x2, y2):
	(rise, run) = (abs(y2 - y1), abs(x2 - x1))
	if rise == 0 or run == 0:
		return 1
	factor = gcd(rise, run)
	return line_len(0, 0, rise // factor, run // factor)
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = [int(x) for x in input().split()]
	(lng, shrt) = (line_len(x1, y1, x2, y2), g(x1, y1, x2, y2))
	print(round(lng / shrt) - 1)


import fractions
for i in range(int(input())):
	(x1, y1, x2, y2) = (int(x) for x in input().split())
	(dx, dy) = (abs(x2 - x1), abs(y2 - y1))
	print(fractions.gcd(dx, dy) - 1)


import math
from fractions import gcd, Fraction
from decimal import Decimal

def numrocks(x1, y1, x2, y2):
	if x2 == x1:
		return abs(y1 - y2) - 1
	elif y2 == y1:
		return abs(x1 - x2) - 1
	else:
		div = gcd(abs(y2 - y1), abs(x2 - x1))
		return int(div - 1)
N = int(input().strip())
for i in range(0, N):
	(x1, y1, x2, y2) = map(int, input().strip().split())
	print(numrocks(x1, y1, x2, y2))


import fractions
t = int(input())
for i in range(t):
	(x1, y1, x2, y2) = [int(x) for x in input().split(' ')]
	if x1 == x2:
		print(max(abs(y2 - y1) - 1, 0))
	elif y1 == y2:
		print(max(abs(x2 - x1) - 1, 0))
	else:
		my = abs(y1 - y2)
		mx = abs(x1 - x2)
		print(fractions.gcd(my, mx) - 1)


import fractions as f
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(f.gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from fractions import gcd
for i in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	a = gcd(abs(x1 - x2), abs(y1 - y2))
	print(a - 1)


from fractions import gcd
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x1 - x2), abs(y1 - y2)) - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(xv, yv) = (abs(x2 - x1), abs(y2 - y1))
	print(gcd(xv, yv) - 1 if yv or xv else 0)


from collections import Counter
from fractions import gcd
from sys import stdin
filou = 'D:\\ZeDaddy\\Documents\\Hack\\Algebra\\HP01.txt'
filou = None
if filou:
	rd = open(filou, 'r')
else:
	rd = stdin

def cnv(lg):
	(X1, Y1, X2, Y2) = list(map(int, lg.split()))
	g = gcd(abs(X2 - X1), abs(Y2 - Y1))
	return g - 1
entree = rd.read(10000000)
lin = list(entree.splitlines())[1:]
for s in lin:
	print(cnv(s))


def GCD(a, b):
	while a != b:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a
T = int(input())
for i in range(0, T):
	(x1, y1, x2, y2) = map(int, input().split())
	if x1 == x2 and y1 == y2:
		print(0)
	elif x1 == x2:
		print(abs(y2 - y1) - 1)
	elif y1 == y2:
		print(abs(x2 - x1) - 1)
	else:
		gcd = GCD(abs(x2 - x1), abs(y2 - y1))
		print(gcd - 1)


def read_ints():
	return [int(x) for x in input().strip().split()]

def read_int():
	(v,) = read_ints()
	return v

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
T = read_int()
for t in range(T):
	(x1, y1, x2, y2) = read_ints()
	dx = abs(x1 - x2)
	dy = abs(y1 - y2)
	s = gcd(dx, dy)
	print(s - 1)


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	g = gcd(abs(x2 - x1), abs(y2 - y1))
	print(g - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	print(gcd(abs(x1 - x2), abs(y1 - y2)) - 1)


from fractions import gcd
T = int(input())
for i in range(T):
	[x, y, a, b] = [int(r) for r in input().split(' ')]
	X = abs(gcd(x - a, y - b)) - 1
	Y = gcd(y, b)
	f = gcd(X, Y)
	g = int(abs(x - a) / f) - 1
	h = int(abs(y - b) / f) - 1
	d = min
	print(X)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


t = int(input().strip())

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a:
		temp = a
		a = b % a
		b = temp
	return b
for _ in range(t):
	(a, b, x, y) = list(map(int, input().strip().split()))
	ans = gcd(abs(a - x), abs(b - y)) - 1
	print(ans)


import math
t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
while t > 0:
	(x1, y1, x2, y2) = [int(x) for x in input().split(' ')]
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)
	t -= 1


n = int(input())

def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)
while n:
	n -= 1
	(x1, y1, x2, y2) = (int(x) for x in input().split(' '))
	w = abs(x1 - x2)
	h = abs(y1 - y2)
	if w == 0:
		print(max(h - 1, 0))
	elif h == 0:
		print(max(w - 1, 0))
	else:
		x = gcd(w, h)
		print(x - 1)


from fractions import gcd
for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	print(gcd(abs(c - a), abs(d - b)) - 1)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = (int(x) for x in input().split())
	if x1 == x2 or y1 == y2:
		d = abs(x1 - x2) + abs(y1 - y2)
		if d == 0:
			print(0)
		else:
			print(d - 1)
	else:
		d = gcd(abs(x1 - x2), abs(y1 - y2))
		print(d - 1)


import fractions

def gcd(x, y):
	if y == 0:
		return x
	elif x == 0:
		return y
	elif x > y:
		return fractions.gcd(x, y)
	else:
		return fractions.gcd(y % x, x)
for n_trials in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	delta_x = abs(x2 - x1)
	delta_y = abs(y2 - y1)
	print('{}'.format(gcd(delta_x, delta_y) - 1))


t = int(input())

def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)
for _ in range(t):
	(a, b, x, y) = map(int, input().split())
	a = abs(a - x)
	b = abs(b - y)
	print(GCD(a, b) - 1)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	x = abs(x1 - x2)
	y = abs(y1 - y2)
	print(gcd(x, y) - 1)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


def gcd(a, b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a
t = int(input().strip())
for _ in range(t):
	(a, b, x, y) = [int(temp) for temp in input().strip().split(' ')]
	dx = abs(x - a)
	dy = abs(y - b)
	if dx == 0 and dy == 0:
		print(0)
	else:
		g = gcd(dx, dy)
		print(g - 1)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


from fractions import gcd
for i in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(x, y) = (abs(x1 - x2), abs(y1 - y2))
	print(gcd(x, y) - 1)


import fractions
for i in range(int(input())):
	(x1, y1, x2, y2) = input().strip().split()
	(x1, y1, x2, y2) = (int(x1), int(y1), int(x2), int(y2))
	if x1 == x2 or y1 == y2:
		x = max(abs(y2 - y1), abs(x2 - x1)) - 1
		print(0 if x == -1 else x)
	else:
		m = fractions.Fraction(y2 - y1, x2 - x1)
		x = m.denominator
		print(abs((x2 - x1) // x) - 1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
for i in range(n):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


from fractions import gcd

def solve(a, b):
	points = gcd(a, b) - 1
	return points
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().strip().split())
	print(solve(abs(x1 - x2), abs(y1 - y2)))


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


from fractions import gcd
T = int(input())
for i in range(T):
	(x1, y1, x2, y2) = (int(j) for j in input().split())
	n = gcd(y2 - y1, x2 - x1)
	print(abs(n) - 1)


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


gcd = lambda x, y: gcd(y, x) if x > y else y if x == 0 else gcd(y % x, x) if y % x else x
print('\n'.join(map(lambda x, y, s, t: str(gcd(abs(x - s), abs(y - t)) - 1), *zip(*(map(int, input().split()) for _ in range(int(input())))))))


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = input().strip().split(' ')
	(x1, y1, x2, y2) = (int(x1), int(y1), int(x2), int(y2))
	print(gcd(abs(y2 - y1), abs(x2 - x1)) - 1)


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def calculate():
	T = int(input().strip())
	for i in range(T):
		(x1, y1, x2, y2) = [int(x) for x in input().split()]
		X = abs(x2 - x1)
		Y = abs(y2 - y1)
		result = gcd(X, Y) - 1
		print(result)
calculate()


import math
from fractions import gcd
t = int(input())

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
for i in range(t):
	(x1, y1, x2, y2) = [int(x) for x in input().strip().split()]
	B = x2 - x1
	A = y1 - y2
	C = x2 * y1 - x1 * y2
	k = gcd(abs(A), abs(B))
	zer = False
	if not C % k == 0:
		zer = True
	if k > 1 and C % k == 0:
		A //= k
		B //= k
		C //= k
	num_sol = 0
	if x1 > x2:
		(x1, x2) = (x2, x1)
	j = x1 + 1
	if zer:
		num_sol = 0
	elif abs(B) == 1:
		num_sol = abs(x2 - x1) - 1
	elif not x1 == x2:
		num_sol = abs((x2 - x1) // B) - 1
	else:
		num_sol = abs(y2 - y1) - 1
	print(num_sol)


from fractions import gcd

def amount(x1, y1, x2, y2):
	dx = abs(x2 - x1)
	dy = abs(y2 - y1)
	return gcd(dx, dy) - 1
T = int(input())
for _ in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	print(amount(x1, y1, x2, y2))


import sys

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def solve(x1, y1, x2, y2):
	dx = abs(x1 - x2)
	dy = abs(y1 - y2)
	print('dx=%d dy=%d' % (dx, dy), file=sys.stderr)
	if dx == 0 and dy == 0:
		return 0
	if dx == 0:
		return dy - 1
	if dy == 0:
		return dx - 1
	if dx == dy:
		return dx - 1
	g = gcd(dx, dy)
	return g - 1
t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	print(solve(x1, y1, x2, y2))


from fractions import gcd
T = int(input())
for t in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	dx = x2 - x1
	dy = y2 - y1
	res = abs(gcd(dx, dy)) - 1
	print(res)


import sys
lines = sys.stdin.readlines()[1:]

def nwd(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return nwd(b, a % b)
for line in lines:
	line = line.split(' ')
	x1 = int(line[0])
	y1 = int(line[1])
	x2 = int(line[2])
	y2 = int(line[3])
	if x1 == x2:
		print(abs(y1 - y2) - 1)
	else:
		print(nwd(abs(x1 - x2), abs(y1 - y2)) - 1)


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a
T = int(input().strip())
for t in range(T):
	[x1, y1, x2, y2] = [int(i) for i in input().strip().split()]
	dx = max(x1, x2) - min(x1, x2)
	dy = max(y1, y2) - min(y1, y2)
	if x1 == x2:
		print(dy - 1)
	elif y1 == y2:
		print(dx - 1)
	else:
		print(gcd(dx, dy) - 1)


from fractions import gcd
for _ in range(int(input())):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	print(gcd(abs(x2 - x1), abs(y2 - y1)) - 1)


def gcd(a, b):
	(a, b) = (abs(a), abs(b))
	(a, b) = a > b and (a, b) or (b, a)
	while b > 0:
		(a, b) = (b, a % b)
	return a
T = int(input().strip())
for _ in range(T):
	(x1, y1, x2, y2) = list(map(int, input().strip().split()))
	print(gcd(x2 - x1, y2 - y1) - 1)


from fractions import gcd
T = int(input())
for i in range(T):
	s = input().split()
	x1 = int(s[0])
	y1 = int(s[1])
	x2 = int(s[2])
	y2 = int(s[3])
	a = abs(y2 - y1)
	b = abs(x2 - x1)
	print(gcd(a, b) - 1)