Museum

Captain Pitt, touring a famous museum, kept running into guards watching over the precious exhibits at every step. Do we really need so many of them? Wouldn’t a single guard be enough? If only we could find the right spot… he thought.

The museum’s floor plan is a polygon whose vertices lie on integer coordinates. Every edge has length $1$, and the angle between any two adjacent walls is a multiple of $90^\circ$.

Given the floor plan, decide whether there is a spot inside the museum (its coordinates may be real numbers) from which every part of the museum is visible.

The first line contains the number of test cases $Z$ ($1 \le Z \le 10$). The test cases follow, one after another.

Each test case begins with a natural number $N$ ($4 \le N \le 1\,000\,000$), the number of vertices of the floor plan.

The next $N$ lines describe the vertices of the polygon in order. Each line contains two natural numbers $X_i$ and $Y_i$ ($0 \le X_i, Y_i < 1\,000\,000$), where $X_i$ is the first coordinate and $Y_i$ the second.

Every two consecutive points (and also the first and the last) are adjacent vertices of the polygon that represents the floor plan.

For each test case, print on its own line TAK if the desired spot exists, and NIE otherwise.

• The vertices are listed in the order in which they are met while walking along the boundary, either clockwise or counter-clockwise.
• The polygon represents an ordinary museum whose walls do not cross one another.
• Two adjacent walls may form an angle of $180^\circ$ (so three consecutive vertices can be collinear).