Над Берляндией снова сгустились тучи. Армия злого лорда Ван де Марта собирается захватить королевство. На военный совет созванный королём Берляндии Валерием Суровым прибыло n рыцарей. После долгих дискуссий стало ясно, что в королевстве есть ровно n опорных точек (сдача каждого из них врагу равносильна поражению в войне) и каждый рыцарь займёт одну из этих точек.
Берляндия разделена на m + 1 область m заборами, и единственный способ перейти из одной области в другую это перелезть через забор. Каждый забор представляет собой окружность на плоскости, причём никакие два забора не имеют общих точек и ни одна опорная точка не находится на заборе. Вам задано k пар чисел ai, bi. Для каждой пары вам нужно узнать: сколько заборов придётся пересечь рыцарю, находящемуся в опорной точке номер ai, чтобы достигнуть опорной точки bi (в случае если Ван де Март нанесёт первый удар в опорную точку номер bi). Поскольку каждый рыцарь путешествует на коне (а коня непросто перекидывать через забор), то вам нужно для каждой пары найти минимальное число пересечений.
Выходные данные
Выведите ровно k строк, в каждой из которых записано одно число — ответ на соответствующий запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 1
0 0
3 3
2 0 0
1 2
|
1
|
|
2
|
2 3 1
0 0
4 4
1 0 0
2 0 0
3 0 0
1 2
|
3
|