На плоскости живут N бактерий, они находятся в точках с целочисленными координатами. Каждый день бактерии размножаются "делением пополам": берутся все возможные пары бактерий и на середине отрезка их соединяющего рождается новая бактерия. Все старые бактерии при этом умирают. Определить первый день, когда найдутся две бактерии, которые родятся в одном и том же месте или сообщите, что этого никогда не произойдет.
Входные данные
Первая строка входных данных содержит число бактерий N (1 ≤ N ≤ 500). Каждая из следующих N строк содержит 2 целых числа x
i, y
i – координаты i-й бактерии (−10
9 ≤ x
i, y
i ≤ 10
9). Никакие 2 бактерии не располагаются в одной точке.
Выходные данные
Выведите 0, если 2 бактерии никогда не родятся в одном месте. В противном случае выведите минимальное количество дней, через которое это случится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0
1 0
0 1
|
0
|
|
2
|
4
0 0
1 0
0 1
1 1
|
1
|
|
3
|
4
1 1
5 3
7 4
9 5
|
2
|