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) були відповідні маршрути.
