Trên mặt phẳng tọa độ ~ Oxy ~ cho hai điểm nguyên ~ P_1 (x_1, y_1 ) ~ và ~ P_2 (x_2, y_2) ~. Yêu cầu: Hãy cho biết có bao nhiêu điểm nguyên nằm trên đoạn thẳng ~ P_1 P_2 ~ (không tính ~ P_1, P_2 ~)

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên ~ t ~ ~ (1 ≤ t ≤ 10^5) ~ cho biết số lượng testcase
• t dòng tiếp theo, mỗi dòng ghi lần lượt 4 số nguyên ~ x_1, y_1, x_2, y_2 ~ ~ (-10^9 ≤ x_1, y_1, x_2, y_2 ≤ 10^9) ~

Kết quả

• Mỗi testcase ghi kết quả trên một dòng

Ràng buộc

Ví dụ:

Input 1

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

```

Output 1

1
2
6