Giải bài trực tuyến

Cho các đa giác không tự cắt, một đa giác được gọi là đa giác hình sao nếu như tồn tại một điểm nằm trong đa giác mà từ điểm đó có thể nhìn thấy tất cả các điểm nằm trong đa giác đó.
Hai điểm là nhìn thấy nhau có nghĩa là khi nối chúng thì tạo thành 1 đoạn thẳng không cắt bất cứ một cạnh nào của đa giác.
Hãy kiểm tra xem đa giác có phải là đa giác hình sao không?.

Input

Gồm một số test, mỗi test dòng đầu là n (n <= 50) (số đỉnh của đa giác).
Tiếp theo là n cặp số nguyên x, y (-10000 <= x, y <= 10000) mô tả tọa độ của các đỉnh đi theo một chiều nhất định (ngược hoặc thuận chiều kim đồng hồ).
Kết thúc test là số 0

Output

Ghi ra 1 hay 0 trên một dòng tương ứng nếu đa giác là hình sao hoặc không là hình sao.

Example

Input:
3
0 0
0 1
1 1
6
66 13
96 61
76 98
13 94
4 0
45 68
8
27 21
55 14
93 12
56 95
15 48
38 46
51 65
64 31
0

Output:
1
1
0