Закон Moore гласит, что количество транзисторов на чипе удваивается каждые два года. Удивительно, но этот закон выполняется уже более полувека. Всякий раз, когда существующая технология больше не позволяла увеличивать их количество, исследователи придумывали новые технологии производства, чтобы размещать схемы ещё плотнее. В ближайшем будущем это может означать создание трёхмерных чипов вместо двумерных. Но для этой задачи достаточно двух измерений.

Общая проблема любого двумерного проектирования аппаратуры (например, чипов, видеокарт, материнских плат и так далее) — размещение проводов. При прокладке проводов на аппаратуре необходимость их пересечения создаёт трудности. В месте пересечения приходится использовать специальные устройства, позволяющие двум электрическим проводам проходить один над другим, что удорожает производство.

Наша задача такова: дан проект аппаратуры с несколькими уже размещёнными проводами (все они являются отрезками прямых). Также заданы начальная и конечная точки нового проводного соединения. Требуется определить минимальное количество существующих проводов, которые придётся пересечь, чтобы соединить эти точки. Соединение не обязано быть прямой линией. Единственное требование: оно не может пересекать точку, в которой уже соприкасаются или пересекаются два или более провода.

Рисунок L.1: Первый пример входных данных.

На рисунке L.1 показан первый пример входных данных. Восемь существующих проводов образуют пять квадратов. Начальная и конечная точки нового соединения находятся соответственно в самом левом и самом правом квадратах. Чёрная пунктирная линия показывает, что прямое соединение пересекло бы четыре провода, тогда как оптимальное решение пересекает только два (синяя кривая).

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

Входные данные состоят из одного тестового случая. Первая строка содержит пять целых чисел $m,x_0,y_0,x_1,y_1$: количество существующих проводов ($m \le 100$), а также начальную и конечную точки, которые нужно соединить. Затем следуют $m$ строк, каждая из которых содержит четыре целых числа $x_a,y_a,x_b,y_b$, описывающих существующий провод ненулевой длины от $(x_a,y_a)$ до $(x_b,y_b)$. Абсолютное значение каждой входной координаты меньше $10^5$. Каждая пара проводов имеет не более одной общей точки, то есть провода не перекрываются. Начальная и конечная точки нового провода не лежат на существующих проводах.

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

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

Примеры

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

8 3 3 19 3
0 1 22 1
0 5 22 5
1 0 1 6
5 0 5 6
9 0 9 6
13 0 13 6
17 0 17 6
21 0 21 6

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

2

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

1 0 5 10 5
0 0 10 10

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

0