Туристу набридло подорожувати уздовж координатної вісі, тому він вирішив помандрувати ще по координатній площині. Він розпочинає зі своєї бази в точці \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}, він, не зупиняючись, рухається до своєї бази. Турист вважає свій маршрут неприємним, якщо існує така пряма, що він уздовж неї не рухався, і разом з тим перетинав її строго більше двох разів. Якщо маршрут не є неприємним, турист вважає його приємним. Турист вважає, що перетинав пряму, якщо в деякий момент часу перебував у одній півплощині відносно неї, а через деякий дуже малий проміжок часу --- в іншій півплощині (сама пряма не належить жодній з півплощин). Напишіть програму, яка, прочитавши описи кількох маршрутів, визначить, чи приємний кожен з них. \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}