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.

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.

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)\)

Example

Sample input

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

Sample output

NO
YES
YES
YES
YES