교차

입력으로 주어진 선분과 직사각형이 서로 교차하는지 판별하는 프로그램을 작성하시오.

예를 들어 선분의 시작점이 $(4, 9)$, 끝점이 $(11, 2)$이고, 직사각형의 한 모서리가 $(1, 5)$, 그 반대쪽 모서리가 $(7, 1)$인 경우, 이 선분과 직사각형은 서로 교차하지 않는다.

선분과 직사각형이 교차한다는 것은 두 도형이 적어도 한 점을 공유한다는 뜻이다. 입력으로 주어지는 좌표는 모두 절댓값이 $50$ 이하인 정수이지만, 두 도형의 교점은 정수 좌표가 아닐 수도 있다. 직사각형의 넓이는 $0$일 수도 있다(즉, 선분이나 하나의 점으로 축소될 수 있다).

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 공백으로 구분된 여덟 개의 정수 xstart ystart xend yend xleft ytop xright ybottom가 주어진다.

• $(xstart, ystart)$는 선분의 시작점, $(xend, yend)$는 선분의 끝점이다.
• $(xleft, ytop)$와 $(xright, ybottom)$은 직사각형의 서로 마주 보는 두 모서리의 좌표이다.

변수 이름의 left, right, top, bottom은 실제 방향(왼쪽·오른쪽·위·아래)을 뜻하지 않으며, 이름이 그렇게 지어진 것은 우연의 일치일 뿐이다. 모든 좌표는 절댓값이 $50$ 이하인 정수이다.

각 테스트 케이스마다 선분과 직사각형이 교차하면 T를, 교차하지 않으면 F를 한 줄에 하나씩 출력한다. 선분의 두 끝점이 모두 직사각형 내부에 있는 경우에도 교차하는 것으로 보아 T를 출력한다.