문제

당신은 $N \times M$ 크기의 격자판 모양의 미로에 갇혀 있다. 격자의 각 칸은 빈 공간(0) 또는 벽(1)으로 이루어져 있다. 당신은 빈 공간에서 상하좌우로 인접한 빈 공간으로 이동할 수 있다. 한 번 이동하는 데에는 1초가 소요된다.

미로를 탈출하기 위해서는 격자판의 외곽에 위치한 빈 공간 중 한 곳에 도달해야 한다. 격자의 외곽이란 $1$행, $N$행, $1$열, 또는 $M$열에 속한 칸들을 의미한다.

여러 개의 쿼리가 주어질 때, 각 쿼리에서 지정한 위치 $(r, c)$에서 시작하여 미로를 탈출하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오. 만약 시작 위치가 이미 외곽이라면 탈출 시간은 $0$이며, 어떤 방법을 써도 외곽에 도달할 수 없다면 $-1$을 출력한다.

입력

첫째 줄에 격자의 세로 크기 $N$과 가로 크기 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 500$)

둘째 줄부터 $N$개의 줄에 걸쳐 격자의 상태가 주어진다. 각 줄에는 $M$개의 정수가 공백으로 구분되어 주어지며, 0은 빈 공간, 1은 벽을 의미한다.

그다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100,000$)

이어서 $Q$개의 줄에 걸쳐 각 쿼리를 나타내는 두 정수 $r, c$가 주어진다. 이는 당신의 시작 위치가 $r$행 $c$열임을 의미한다. ($1 \le r \le N, 1 \le c \le M$)

출력

각 쿼리에 대해, 해당 위치에서 외곽의 빈 공간으로 이동하기 위한 최소 시간을 한 줄에 하나씩 출력한다. 시작 위치가 벽이거나 외곽으로 나갈 수 없는 경우 -1을 출력한다.

예제 입력 1

3 4
1 0 1 1
1 0 0 1
1 1 0 1
4
1 2
2 2
2 3
3 3

예제 출력 1

0
1
1
0

예제 입력 2

5 5
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1
1
2 2

예제 출력 2

-1