Given $q$ questions. In each question, you are given four points $A(x_A,y_A),B(x_B,y_B),C(x_C,y_C),D(x_D,y_D)$. Determine if line segment $AB$ intersect with line segment $CD$ (i.e. they have at least one common point). It is guaranteed that $A \neq B$ and $C \neq D$.
### Input
- The first line contains an integer $q$.
- The next $q$ lines, each line contains eight integers $x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D$.
### Output
- Print $q$ lines. Each line, print `YES` if two line segments in the corresponding question interesect, otherwise print `NO`.
### Constraints
- $1 \le q \le 10^5$.
- $-10^9 \le x, y \le 10^9$.
### Example
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
```
Output:
```
NO
YES
YES
YES
YES
```
