题目描述

在赛博虚拟世界“矩阵”中，存在一个由 $n \times n$ 个像素点构成的光影核心。每个像素点只有两种状态：“暗状态 (0)” 或 “光状态 (1)”。

为了传输数据，网络信号必须在“光”与“暗”之间不断交替跳跃。具体规则如下：

• 如果你当前处于一个暗状态 (0) 的像素点，你只能移动到上下左右相邻 $4$ 个格中某个光状态 (1) 的像素点上。
• 同理，如果你当前处于一个光状态 (1) 的像素点，你只能移动到上下左右相邻 $4$ 个格中某个暗状态 (0) 的像素点上。

只要满足这个“光暗交替”的规则，信号就可以无限次移动。这群能够互相到达的像素点，在网络中被称为一个“共鸣网络”。

现在，网络管理员面临 $m$ 次探测任务。对于每次探测给出的起始像素点位置，请你计算出：从这一格出发，信号总共可以传播到多少个不同的像素点（包含起始格自身）？

输入格式

第一行包含两个正整数 $n$ 和 $m$。$n$ 表示光影核心矩阵的边长，$m$ 表示探测询问的次数。

接下来的 $n$ 行，每行包含 $n$ 个字符（只可能是 0 或 1，字符之间没有空格），表示整个光影矩阵的初始状态。

接下来的 $m$ 行，每行包含两个用空格分隔的正整数 $i$ 和 $j$，表示一次探测的起始坐标为第 $i$ 行第 $j$ 列。

输出格式

输出共 $m$ 行，对于每一次探测询问，输出该点所能到达的像素点总数。

输入输出样例 #1

输入 #1

2 2
01
10
1 1
2 2

输出 #1

4
4

说明/提示

样例解释： 对于这个 $2 \times 2$ 的矩阵，通过 $0 \leftrightarrow 1$ 的交替移动规则，所有的格子都可以互相到达，因此每个询问的答案都是 $4$。

数据规模：

• 对于 $20\%$ 的数据，$n \leq 10$；
• 对于 $40\%$ 的数据，$n \leq 50$；
• 对于 $50\%$ 的数据，$m \leq 5$；
• 对于 $60\%$ 的数据，$n, m \leq 100$；
• 对于 $100\%$ 的数据，$1 \le n \leq 1000$，$1 \le m \leq 100000$。