Cho \(q\) truy vấn. Mỗi truy vấn cho hai điểm nguyên \(A(x_1,y_1)\) và \(B(x_2,y_2)\). Hãy đếm số điểm nguyên nằm trên đoạn thẳng \(AB\) (bao gồm cả hai đầu mút).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) (\(|x_i|, |y_i| \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra một số nguyên là số điểm nguyên trên đoạn thẳng.

Ví dụ

Input:

3
0 0 4 0
0 0 3 3
1 1 4 4

Output:

5
4
4

Ràng buộc

• 30% số điểm: \(q \le 100\).
• 70% số điểm còn lại: không có ràng buộc gì thêm.