Туристу надоело путешествовать вдоль координатной ост, поэтому он решил постранствовать ещё по координатной плоскости. Он начинает со своей базы в точке 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) были соответствующие маршруты.