No testdata at current.

题目描述

有一个 $n\times n$ 的 $0/1$ 矩阵，其中 $0$ 表示陆地，$1$ 表示河流。

渡过河流必须要做一个竹筏，并且上岸时竹筏必须丢弃。不论是在陆地上还是河流中，你都可以向周围的八连通移动。到达地图边界即可逃出地图。

有 $k$ 次询问，每次询问当你的位置在 $(x,y)$ 时，逃出地图最少需要制作几个竹筏。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行，每行 $n$ 个数字，描述地图。

接下来 $k$ 行，每行两个正整数 $(x,y)$ ，表示一个询问

输出格式

输出仅包括一行，按输入顺序每行对于一个询问输出答案，数字间用空格隔开，行末换行并没有空格。

样例

样例输入

9 3
000000000
011111110
010101010
011000110
010000010
010111010
010101010
011111110
000000000
1 3
3 3
4 6

样例输出

0 1 1

数据范围与提示

对于 $20\%$ 的数据，$n\le10$。

对于 $40\%$ 的数据，$n \le100$，$k\le10$。

对于 $60\%$ 的数据，$n \le1000$，$k\le100$。

对于 $100\%$ 的数据，$1 \le n \le100$，$k\le40000$。