A128505.迷宫寻路

$Sherry$ 在上学路上误入空洞迷宫，这个迷宫是一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列上有一个数字 $a_{i,j}$。

• 如果 $a_{i,j}=0$，则该位置为空地，可以移动到该位置。
• 如果 $a_{i,j}=1$，则该位置为障碍物，不能移动到该位置。
• 只能移动到当前位置的上下左右四个方向之一，且只能移动到相邻的格子。

$Sherry$ 会出现在迷宫的某个空地位置。$Sherry$ 每次可以选择向上、下、左、右中的一个方向移动一格，不能移动到障碍物上。

她希望尽快离开迷宫。当她移动到行号小于 $1$ 或大于 $n$，或列号小于 $1$ 或大于 $m$ 的位置时，她就成功离开迷宫。

现在，你要帮 $Sherry$ 算一算，对于每次询问的初始位置，她在至少多少次移动后会离开迷宫，或报告她永远不会离开迷宫。

第一行输入三个整数 $n,m,k$，分别表示迷宫的行数 $n$、列数 $m$ 和询问次数 $k$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $a$。

接下来 $k$ 行，每行两个整数 $x_{i},y_{i}$，表示第 $i$ 次查询的初始位置在 $x_{i}$ 行 $y_{i}$ 列。

保证每次询问的初始位置均为空地。

输出 $k$ 行，每行一个整数，表示一次查询的答案。如果本次查询中她永远无法离开迷宫，输出 $-1$。

数据范围

$1\le n,m,k\le 1000,0\le a_{i,j}\le 1,1\le x_{i}\le n,1\le y_{i}\le m$

保证每次询问的初始位置均为空地。