Bạn được cho 2 đoạn thẳng. Đoạn thẳng thứ nhất được nối từ điểm \((x_1, y_1)\) đến \((x_2, y_2)\). Đoạn thứ hai được nối từ điểm \((x_3, y_3)\) đến \((x_4, y_4)\). Nhiệm vụ của bạn là tìm xem hai đoạn thẳng này có cắt nhau không (tức là 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ứ 1 số nguyên dương \(t\): Số truy vấn cần trả lời
• \(t\) dòng tiếp theo, mỗi dòng gồm tám số nguyên \(x_1,y_1, x_2,y_2, x_3,y_3, x_4,y_4\) miêu tả hai đoạn thẳng cần xét

Constraints

• \(1 \leq t \leq 10^5\)
• \(-10^9 \leq x_1,y_1, x_2,y_2, x_3,y_3, x_4,y_4 \leq 10^9\)
• \((x_1,y_1) \neq (x_2,y_2)\)
• \((x_3,y_3) \neq (x_4,y_4)\)

Output

• Với mỗi truy vấn, hãy in ra YES nếu hai đoạn thẳng được cho có ít nhất một điểm chung. Ngược lại hãy in NO

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