Правильный шестиугольник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Женя решил подготовить на Новый Год украшения на ёлку. А самое лучшее украшение — это правильный шестиугольник! Поэтому Женя поручил своей младшей сестре Кате сделать несколько правильных шестиугольников.

Работу Женя организовал следующим образом. Сначала Катя на клетчатом листке бумаги рисует шесть точек в узлах сетки так, чтобы получился выпуклый шестиугольник. Затем Женя проверяет, является ли этот шестиугольник правильным. Если шестиугольник правильный, то Катя его вырезает и вешает на ёлку, а иначе Катя выбрасывает этот листок.

Женя догадывается, что правильный шестиугольник в узлах сетки может не существовать, поэтому допускает некоторые отклонения. Женя будет считать, что выпуклый шестиугольник является правильным, если выполнены три условия:

1. $$$\frac{\mathrm{SideMax}}{\mathrm{SideMin}} \le \frac{111}{100}$$$, где $$$\mathrm{SideMax}$$$ и $$$\mathrm{SideMin}$$$ — максимальная и минимальная длина стороны многоугольника.

2. $$$\frac{\mathrm{DiagMax}}{\mathrm{DiagMin}} \le \frac{111}{100}$$$, где $$$\mathrm{DiagMax}$$$ и $$$\mathrm{DiagMin}$$$ — максимальная и минимальная длина диагонали, соединяющей противоположные вершины шестиугольника.

3. Внутри шестиугольника существует точка $$$O$$$ в узле сетки такая, что $$$\frac{\mathrm{DistMax}}{\mathrm{DistMin}} \le \frac{111}{100}$$$, где $$$\mathrm{DistMax}$$$ и $$$\mathrm{DistMin}$$$ — максимальная и минимальная длина отрезка соединяющего точку $$$O$$$ с вершиной шестиугольника.

Входные данные

В первой строке дано единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество шестиугольников, которые сделала Катя.

В следующих строках заданы $$$t$$$ шестиугольников. Входные данные для каждого шестиугольника занимают шесть строк. В шести строках, задающих очередной шестиугольник, даны через пробел по два целых числа $$$X$$$, $$$Y$$$ ($$$0 \le X, Y \le 1000$$$) — координаты очередной вершины шестиугольника.

Вершины каждого шестиугольника даны в порядке обхода его вершин по часовой стрелке. Гарантируется, что каждый заданный шестиугольник является строго выпуклым.

Выходные данные

В единственной строке выведите единственную строку $$$S$$$ длины $$$t$$$. Еcли $$$i$$$-й шестиугольник является правильным по критерию Жени, то $$$i$$$-й символ строки $$$S$$$ должен быть равен '1', а иначе $$$i$$$-й символ строки $$$S$$$ должен быть равен '0'.

Пример

Входные данные

    20 32 66 68 36 02 00 11 22 23 12 01 0

Выходные данные

    10