Туристу надоело путешествовать вдоль координатной ост, поэтому он решил постранствовать ещё по координатной плоскости. Он начинает со своей базы в точке \textbf{A_1} с координатами \textbf{x_1} \textbf{y_1}, движется кратчайшим маршрутом к определённой памятке \textbf{A_2} с координатами \textbf{x_2} \textbf{y_2}, дальше, не останавливаясь, движется кратчайшим маршрутом к заданной памятке \textbf{A_3} с координатами \textbf{x_3} \textbf{y_3}, и так далее. Добравшись к последней заданной памятке \textbf{A_n} с координатами \textbf{x_n} \textbf{y_n}, он, не останавливаясь, движется к своей базе. Турист считает свой маршрут \textit{неприятным}, если существует такая прямая, вдоль которой он не двигался, и, вместе с тем пересекал её строго больше двух раз. Якщо маршрут не является неприятным, турист считает его \textit{приятным}. Турист предполагает, что пересекал прямую, если в некоторый момент времени находился в одной полуплоскости относительно неё, а через некоторый очень малый промежуток времени --- в другой полуплоскости (пересекаемая прямая не принажлежит ни одной из полуплоскостей). Напишите программу, которая, прочитав описания нескольких маршрутов, определит, приятен ли каждый из них. \InputFile Программа должна прочитать сначала количество маршрутов \textbf{K} (\textbf{2} ≤ \textbf{K} ≤ \textbf{12}), потом \textbf{K} однотипных блоков, каждый из которых описывает маршрут. Кождый блок описания маршрута начинается числом \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{98765}), далее идёт \textbf{n} пар чисел, не превышающихь \textbf{10^8} по абсолютной величине --- координаты \textbf{x_1} \textbf{y_1} \textbf{x_2} \textbf{y_2} … \textbf{x_n} \textbf{y_n}. Все числа всех маршрутов записаны в одной строке и разделены единичными пробелами. Суммарное количество всех вершин всех маршрутов, которые программа должна обработать за один запуск, не превышает \textbf{123456}. \OutputFile Программа должна вывести в одну строку \textbf{K} разделённых пробелами нулей и/или единиц, которые обозначают, приятными (\textbf{1}) или неприятными (\textbf{0}) были соответствующие маршруты. \includegraphics{https://static.e-olymp.com/content/39/3981af3874ed07f97d67b8cceafdf72c89974d3d.jpg}