Tourist#2773
The tourist has grown tired of traveling along the coordinate axes and has decided to travel across the coordinate plane. He starts from his base at point A_1 with coordinates x_1 y_1, travels in a straight line to the landmark A_2 at coordinates x_2 y_2, then, without stopping, continues in a straight line to the next landmark A_3 at x_3 y_3, and so on. After reaching the last given landmark A_n at x_n y_n, he returns directly to his base. The tourist considers his route unpleasant if there exists a straight line that he did not travel along, but crossed strictly more than twice. If no such line exists, he considers the route pleasant.
The tourist considers that he has crossed a line if at one moment in time he was in one half-plane relative to it, and, after a very short time, he is in the other half-plane (the line itself does not belong to either half-plane).
Write a program that, after reading the descriptions of several routes, determines for each whether it is pleasant.
The program should first read the number of routes (2 \leq K \leq 12). Then identical blocks follow, each describing a route. Each block starts with the number (2 \leq n \leq 98765), followed by pairs of numbers, each not exceeding 10^8 in absolute value — the coordinates x_1 y_1 x_2 y_2 x_n y_n. All numbers for all routes are written in a single line and separated by single spaces. The total number of vertices among all routes that the program must process in one run does not exceed .
The program should print a single line of zeros and/or ones separated by spaces, indicating whether the corresponding routes are pleasant () or unpleasant ().
Example 1