Tourist
Туристу надоело путешествовать вдоль координатной ост, поэтому он решил постранствовать ещё по координатной плоскости. Он начинает со своей базы в точке A_1 с координатами x_1 y_1, движется кратчайшим маршрутом к определённой памятке A_2 с координатами x_2 y_2, дальше, не останавливаясь, движется кратчайшим маршрутом к заданной памятке A_3 с координатами x_3 y_3, и так далее. Добравшись к последней заданной памятке A_n с координатами x_n y_n, он, не останавливаясь, движется к своей базе. Турист считает свой маршрут неприятным, если существует такая прямая, вдоль которой он не двигался, и, вместе с тем пересекал её строго больше двух раз. Якщо маршрут не является неприятным, турист считает его приятным.
Турист предполагает, что пересекал прямую, если в некоторый момент времени находился в одной полуплоскости относительно неё, а через некоторый очень малый промежуток времени — в другой полуплоскости (пересекаемая прямая не принажлежит ни одной из полуплоскостей).
Напишите программу, которая, прочитав описания нескольких маршрутов, определит, приятен ли каждый из них.
Входные данные
Программа должна прочитать сначала количество маршрутов K (2 ≤ K ≤ 12), потом K однотипных блоков, каждый из которых описывает маршрут. Кождый блок описания маршрута начинается числом n (2 ≤ n ≤ 98765), далее идёт n пар чисел, не превышающихь 10^8 по абсолютной величине — координаты x_1 y_1 x_2 y_2 … x_n y_n. Все числа всех маршрутов записаны в одной строке и разделены единичными пробелами. Суммарное количество всех вершин всех маршрутов, которые программа должна обработать за один запуск, не превышает 123456.
Выходные данные
Программа должна вывести в одну строку K разделённых пробелами нулей и/или единиц, которые обозначают, приятными (1) или неприятными (0) были соответствующие маршруты.
