박물관

피트 선장은 유명한 박물관을 둘러보다가 발걸음을 옮길 때마다 값비싼 전시품을 지키는 경비원들과 마주쳤다. 정말 이렇게 많은 경비원이 필요할까? 경비원 한 명이면 충분하지 않을까? 알맞은 자리 하나만 찾을 수 있다면… 하고 그는 생각했다.

박물관의 평면도는 다각형이며, 모든 꼭짓점은 정수 좌표 위에 있고, 모든 변의 길이는 $1$이며, 이웃한 두 벽이 이루는 각은 모두 $90^\circ$의 배수이다.

박물관 평면도가 주어질 때, 박물관의 모든 부분을 볼 수 있는 자리(좌표는 실수여도 된다)가 존재하는지 판단하여라.

첫째 줄에 테스트 케이스의 개수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 케이스가 차례로 주어진다.

각 테스트 케이스는 박물관 평면도의 꼭짓점 개수를 나타내는 자연수 $N$ ($4 \le N \le 1\,000\,000$)으로 시작한다.

다음 $N$개의 줄에는 다각형의 꼭짓점이 순서대로 주어진다. 각 줄에는 두 자연수 $X_i$와 $Y_i$ ($0 \le X_i, Y_i < 1\,000\,000$)가 주어지며, $X_i$는 첫 번째 좌표, $Y_i$는 두 번째 좌표를 뜻한다.

인접한 두 점(그리고 첫 번째 점과 마지막 점)은 박물관 평면도를 나타내는 다각형에서 서로 이웃한 꼭짓점이다.

각 테스트 케이스마다, 원하는 자리가 존재하면 TAK을, 존재하지 않으면 NIE를 한 줄에 출력한다.

• 다각형의 꼭짓점은 그 둘레를 시계 방향 또는 반시계 방향으로 따라갈 때 만나게 되는 순서대로 나열되어 있다.
• 이 다각형은 벽이 서로 교차하지 않는 일반적인 박물관을 나타낸다.
• 이웃한 두 벽은 $180^\circ$의 각을 이룰 수도 있다(즉, 한 직선 위에 놓인 세 꼭짓점이 있을 수 있다).