해류

넓은 수역 위의 배에게 강한 해류는 위험할 수 있지만, 신중히 계획하면 배가 목적지에 도달하도록 해류를 이용할 수도 있다. 당신이 할 일은 그 계획을 돕는 것이다.

각 위치에서 해류는 어떤 방향으로 흐른다. 선장은 해류의 흐름을 그대로 타고 에너지를 전혀 쓰지 않고 이동하거나, 그 외의 방향으로 한 칸 이동하는 데 에너지 1을 쓸 수 있다. 배는 항상 북, 남, 동, 서, 북동, 북서, 남동, 남서의 여덟 방향 중 하나로 움직인다. 배는 호수의 경계를 벗어날 수 없다. 최소 에너지로 목적지에 도달하는 전략을 세우도록 도와라.

호수는 직사각형 격자로 표현된다. 입력의 첫째 줄에는 격자의 행의 수 $r$ 과 열의 수 $c$ 가 주어진다. 격자의 행과 열은 각각 최대 1000개이다. 이어지는 $r$ 개의 줄에는 각각 정확히 $c$ 개의 문자가 있으며, 각 문자는 $0$ 부터 $7$ 까지의 숫자이다. 문자 $0$ 은 해류가 북쪽(격자에서 위쪽, 즉 행 번호가 감소하는 방향)으로 흐름을, $1$ 은 북동쪽, $2$ 는 동쪽(열 번호가 증가하는 방향), $3$ 은 남동쪽을 뜻하며, 아래와 같이 시계 방향으로 이어진다.

7 0 1
 \|/
6-*-2
 /|\
5 4 3

격자 다음 줄에는 이동의 횟수 $n$ 이 하나의 정수로 주어지며, $n$ 은 최대 50이다. 이어지는 $n$ 개의 줄에는 각 이동이 네 정수 $r_s$, $c_s$, $r_d$, $c_d$ 로 주어지는데, 이는 각각 출발점과 도착점의 행과 열이다. 행과 열의 번호는 $1$ 부터 시작한다.

각 이동마다, 출발점에서 도착점까지 가는 데 필요한 최소 에너지 양을 하나의 정수로 한 줄에 출력한다.