There are two line segments: the first goes through the points $(x_1,y_1)$ and $(x_2,y_2)$ , and the second goes through the points $(x_3,y_3)$ and $(x_4,y_4)$ .

Your task is to determine if the line segments intersect, i.e., they have at least one common point.

The first input line has an integer $t$ : the number of tests.

After this, there are $t$ lines that describe the tests. Each line has eight integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , $x_3$ , $y_3$ , $x_4$ and $y_4$ .

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

For each test, print "YES" if the line segments intersect and "NO" otherwise.