Do the segments intersect - 2

Given four points (A), (B), (C), and (D), determine if the line segments (AB) and (CD) share at least one common point.

The program should handle all scenarios, including cases where the segments overlap or when (A = B) or (C = D), which means one or both segments reduce to a single point.

Input

Read the input from standard input. The first line contains an integer (N) ((1 $\le$ N $\le$ 5)), representing the number of segment pairs in the test. This is followed by (N) groups of two lines each. The first line of each group provides the coordinates of segment (AB) in the format (A_x) (A_y) (B_x) (B_y). The second line of each group provides the coordinates of segment (CD) in the format (C_x) (C_y) (D_x) (D_y). All coordinates are integers and do not exceed one million in absolute value.

Output

For each group, output YES on a separate line if the segments intersect, or NO if they do not.

Examples