Tourist

The tourist, weary of traveling along the coordinate axis, has decided to explore the coordinate plane. He begins his journey from his base at point (A_1) with coordinates ((x_1, y_1)), traveling the shortest path to the landmark (A_2) at ((x_2, y_2)). Without pausing, he continues along the shortest path to the next landmark (A_3) at ((x_3, y_3)), and so forth. Upon reaching the final landmark (A_n) at ((x_n, y_n)), he returns directly to his base. The tourist finds his route unpleasant if there exists a line that he crosses strictly more than twice without traveling along it. If no such line exists, he considers the route pleasant.

The tourist defines crossing a line as moving from one half-plane to the other relative to that line, without the line itself being part of either half-plane.

Write a program that, after reading the descriptions of several routes, determines whether each route is pleasant.

Input

First, the program should read the number of routes (K) ((2 $\le$ K $\le$ 12)), followed by (K) identical blocks, each describing a route. Each block begins with the number (n) ((2 $\le$ n $\le$ 98765)), followed by (n) pairs of numbers, each not exceeding (10^8) in absolute value, representing the coordinates ((x_1, y_1), (x_2, y_2), ..., (x_n, y_n)). All numbers for all routes are provided in a single line, separated by spaces. The total number of vertices across all routes processed in one run will not exceed 123456.

Output

The program should output a single line containing (K) zeros and/or ones, separated by spaces, indicating whether the corresponding routes are pleasant ((1)) or unpleasant ((0)).

Examples