Hai Đoạn Có Gặp Nhau?

Mỗi bộ kiểm tra cho hai đoạn thẳng đóng $AB$ và $CD$. Hãy xác định chúng có ít nhất một điểm chung hay không.

Một giao điểm tại đầu mút cũng được tính. Nếu hai đoạn thẳng hàng, chúng giao nhau khi phần của chúng trên đường thẳng chồng lấn ít nhất một điểm.

Input

• Dòng đầu chứa số nguyên $t$ - số bộ kiểm tra.
• Mỗi dòng tiếp theo chứa tám số nguyên $x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D$.

Output

• Với mỗi bộ kiểm tra, in YES nếu hai đoạn có điểm chung, ngược lại in NO.

Constraints

• $1\le t\le 10^5$.
• Mọi tọa độ nằm trong $[-10^9,10^9]$.
• $A\ne B$ và $C\ne D$.

Scoring

• Subtask $1$ ($50$ điểm): $t\le 2000$ và trị tuyệt đối tọa độ không quá $10^4$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

5
0 0 4 4 0 4 4 0
0 0 4 0 4 0 7 3
0 0 6 0 2 0 8 0
0 0 2 0 3 0 5 0
-2 -2 2 2 0 0 0 5

YES
YES
YES
NO
YES