Intersection

Write a program that determines whether a given line segment and rectangle intersect.

For example, suppose the segment has start point $(4, 9)$ and end point $(11, 2)$, and the rectangle has one corner at $(1, 5)$ and the opposite corner at $(7, 1)$. In this case the segment and the rectangle do not intersect.

The segment and the rectangle intersect if they share at least one point. All coordinates given in the input are integers whose absolute value is at most $50$, but the point of intersection need not have integer coordinates. The rectangle's area may be $0$ (that is, it may degenerate to a segment or a single point).

The first line contains the number of test cases $T$. Each test case is given on a single line as eight space-separated integers xstart ystart xend yend xleft ytop xright ybottom.

• $(xstart, ystart)$ is the segment's start point and $(xend, yend)$ is its end point.
• $(xleft, ytop)$ and $(xright, ybottom)$ are the coordinates of two opposite corners of the rectangle.

The words left, right, top, and bottom in the variable names do not indicate actual directions; the names are merely a coincidence. Every coordinate is an integer with absolute value at most $50$.

For each test case, print T if the segment and the rectangle intersect, or F otherwise, one result per line. When both endpoints of the segment lie inside the rectangle, that also counts as intersecting, so print T.