说明

有一个仅由数字0与1组成的$n×n$格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）

输入格式

第1行为两个正整数$n,m$

下面$n$行，每行$n$个字符，字符只可能是0或者1，字符之间没有空格

接下来$m$行，每行2个用空格分隔的正整数$i,j$，对应了迷宫中第$i$行第$j$列的一个格子，询问从这一格开始能移动到多少格

输出格式

$m$行，对于每个询问输出相应答案。

样例

2 2
01
10
1 1
2 2

4
4

数据范围

• 对于20%的数据，$n≤10$
• 对于40%的数据，$n≤50$
• 对于50%的数据，$m≤5$
• 对于60%的数据，$n≤100,m≤100$
• 对于100%的数据，$n≤1000,m≤100000$