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.

Input

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

Output

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

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 \neq x_2\) or \(y_1 \neq y_2\)
• \(x_3 \neq x_4\) or \(y_3 \neq 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