Giao điểm đoạn thẳng

Trong mặt phẳng tọa độ, cho hai đoạn thẳng. Đoạn thẳng thứ nhất được xác định bởi hai điểm đầu mút \(P_1=(x_1, y_1)\) và \(P_2=(x_2, y_2)\). Đoạn thẳng thứ hai được xác định bởi hai điểm đầu mút \(P_3=(x_3, y_3)\) và \(P_4=(x_4, y_4)\).

Nhiệm vụ của bạn là xác định xem hai đoạn thẳng này có cắt nhau hay không, tức là chúng có ít nhất một điểm chung.

Bạn phải trả lời \(t\) truy vấn có dạng như trên.

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\) (\(1 \le t \le 10^5\)), là số lượng các truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng chứa tám số nguyên \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\) (\(-10^9 \le x_i, y_i \le 10^9\)) mô tả hai đoạn thẳng.

Output

• Với mỗi truy vấn, in ra trên một dòng:

• YES nếu hai đoạn thẳng có điểm chung.

• NO nếu ngược lại.

Example

5
1 1 5 3 1 2 4 3
1 1 5 3 1 1 4 3
1 1 5 3 2 3 4 1
1 1 5 3 2 4 4 1
1 1 5 3 3 2 7 4

NO
YES
YES
YES
YES