Przecięcie odcinków

Limit czasu: 1s | Limit pamięci: 64MB

Dane są dwa odcinki: pierwszy wyznaczony przez punkty $(x_1,y_1)$ i $(x_2,y_2)$, drugi przez punkty $(x_3,y_3)$ i $(x_4,y_4)$. Twoim zadaniem jest ustalenie, czy odcinki przecinają się, tzn. czy mają przynajmniej jeden punkt wspólny.

Wejście

Pierwsza linia wejściowa zawiera liczbę całkowitą $t$: liczbę testów. Następnie następuje $t$ linii opisujących testy. W każdym wierszu znajduje się osiem liczb całkowitych $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$ i $y_4$.

Wyjście

Dla każdego testu wypisz "YES", jeśli odcinki przecinają się, lub "NO", w przeciwnym razie.

Ograniczenia

• $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)$

Przykłady

Wejście 1

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

Wyjście 1

NO
YES
YES
YES
YES