펭귄 Pingvin

펭귄 Zrakoplović은 나는 법을 배우고 싶어 한다.

그가 나는 법을 배울 공간은 한 변의 길이가 $n$인 정육면체이며, $n^3$개의 단위 정육면체로 나뉘어 있다. 각 단위 정육면체는 세 좌표 $(x, y, z)$로 나타내며, $x$, $y$, $z$는 $1$부터 $n$까지의 정수이다. 좌표 $x$는 공간의 왼쪽 끝으로부터의 거리, 좌표 $y$는 앞쪽 끝으로부터의 거리, 좌표 $z$는 높이이다.

이 단위 정육면체들 중 일부에는 구름이 있고, 일부에는 없다.

Zrakoplović은 구름을 무서워해서 구름이 없는 곳으로만 난다. 그는 높이가 $1$인 위치 $(x_s, y_s, z_s)$, 즉 $z_s = 1$인 곳에서 출발해 $(x_e, y_e, z_e)$에 도달하려 한다.

그는 공간의 축 중 하나($x$축, $y$축, $z$축)와 평행한 방향으로 나는 연습을 하고 있다. 한 번의 날갯짓으로 지날 수 있는 단위 정육면체는 최대 하나이다.

날기 전에, Zrakoplović은 목적지에 도달하려면 날갯짓을 몇 번 해야 하는지 알고 싶어 한다. 그 횟수를 구하라.

출발 위치와 도착 위치에는 구름이 없다.