На бесконечном клетчатом поле отмечены три различные клетки: \(A\), \(B\) и \(F\). Выведите длину кратчайшего пути из \(A\) в \(B\), если:
- за один ход можно переходить на любую из четырех соседних по стороне клеток;
- посещать клетку \(F\) — запрещено (она является препятствием).
Выходные данные
Выведите \(t\) строк. \(i\)-я из них должна содержать ответ для \(i\)-го набора входных данных — длину кратчайшего пути из клетки \(A\) в клетку \(B\), если клетка \(F\) запрещена для посещения.
Примечание
Пример возможного кратчайшего пути для первого набора входных данных. 
Пример возможного кратчайшего пути для второго набора входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 1
3 3
2 2
2 5
2 1
2 3
1000 42
1000 1
1000 1000
1 10
3 10
2 10
3 8
7 8
3 7
2 1
4 1
1 1
1 344
1 10
1 1
|
4
6
41
4
4
2
334
|