lot

Danut's grandfather is a bee keeper. Every spring he rents a lot of land and he places his bees there. Because grandpa loves to travel each spring he selects a lot in a different region of the country. The bees, being intelligent, only move within the rented lot and don't go outside the border, which is determined by a closed broken line. In order to optimize pollen collection the bees have to fly from any point of the lot to the hive on a linear trajectory (without changing course). Therefore the following criteria have to be respected when selecting rental lot offers:

  1. Make sure the broken line that marks the lot border is closed.
  2. The segments of the line that cross the border don't intersect themselves, except adjacent segment extremities.
  3. Any two internal lot points may be united by a segment that doesn't cross the border.
  4. Any three consecutive border vertices are not collinear.

Task

The offers received by grandpa contain the descriptions of several lots (see the above image). Write a program that can help Danut select those lots that correspond to the criteria contained in the problem's description.

Input Data

Line one of file lot.in contains a positive integer N – the number of lots described in the file. The description of each lot begins on a line which contains a positive integer Ki – representing the number of border segments of lot i. Next, in order, the descriptions of the vertices of the lot's border, one vertex per line. The description of the vertex is given by its coordinates (x, y) separated by a space. The description of lot i ends in a line containing numbers 0 0.

Output Data

File lot.out will contain N lines. Line i will contain digit 1 if lot i meets the demands of the problem in the description or 0 – if it doesn't.

Restrictions

0 < N <= 20
3 <= Ki <= 1000, i= 1, ..., N
-10000 <= x, y <= 10000
x, y <> 0

Example

lot.in (image)

lot.out

3
4
1 1
1 5
7 5
7 1
0 0
4
-2 -1
-2 -6
-3 -3
-7 -1
0 0
3
-1 1
-3 1
-1 3
0 0

1
0
1

Time limit: 0.1 seconds/test

prof. Sergiu Corlat
Chişinău Moldavian-Turkish High-School
Contact:scorlat@gmail.com