Description

$\hspace{15pt}$在龙之国生活着一群拥有神秘魔力的龙族。他们所生活的地方类似一个大小为 $n\times n$ 的棋盘，由黑白两种格子组成。龙族世代遵守着一条古老的法则：$\textbf{一只龙永远不能连续踏上相同颜色的土地！}$

$\hspace{15pt}$你是一位刚刚成年的年轻龙族，正准备参加修行试炼，龙王赐予你一张地图并向你发出提问：从某个指定的格子出发，最多可以跳跃到多少个格子？（包含起点本身）

$\hspace{15pt}$你在跳跃时只能上下左右移动，不能斜着移动，也不能原地停留。并且不能连续跳相同颜色的格子 （即每次跳跃只能从黑格子跳到白格子 或 从白格子跳到黑格子）。国王龙会向你提问 $q$ 次，每次询问一个起点格子的位置。你需要计算并回答每次提问。

Format

Input

$\hspace{15pt}$第一行包含两个正整数 $n$ 和 $q\,(1\leq n \leq 10^3,\,1\leq q \leq 10^5)$，分别表示魔法棋盘的大小和国王龙的询问次数。

$\hspace{15pt}$接下来 $n$ 行，每行包含一个长度为 $n$ 的、仅由 '0' 或 '1' 组成的字符串，表示棋盘地图。（'0'代表当前位置格子为黑色， '1'代表白色）

$\hspace{15pt}$再接下来 $q$ 行，每行两个整数 $i$ 和 $j \,(1\leq i,j \leq n)$，表示本次询问起点为棋盘上的第 $i$ 行第 $j$ 列的格子。

Output

$\hspace{15pt}$输出 $q$ 行，每行一个整数，表示该次提问中，从对应起点出发最多可跳跃的格子数量（包含起点本身）。

Samples

2 2
01
10
1 1
2 2

4
4

3 2
001
001
110
1 1
3 3

1
4

Note

$\hspace{15pt}$对于第一组样例从 $(1,1)$ 和 $(2,2)$ 走都可以到达包括自己的所有格子所以输出4。