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

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

输入格式

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

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

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

输出格式

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

2 2
01
10
1 1
2 2

4
4

8 45
10011100
01000110
10100011
11001001
11111111
00010010
11010110
00111100
6 7
4 4
2 7
6 4
1 3
6 7
5 7
8 6
8 5
2 5
2 5
1 8
3 1
7 6
8 2
1 5
6 3
7 8
7 1
5 4
1 4
7 3
4 1
2 8
3 1
4 8
8 3
4 8
1 1
5 4
2 5
2 6
7 8
1 2
3 3
6 8
6 4
6 1
2 4
3 6
4 3
3 7
4 3
5 6
3 6

20
20
5
16
3
20
8
4
20
8
8
1
16
20
20
8
16
4
4
20
3
20
1
5
16
8
20
8
16
20
8
8
4
16
16
20
16
4
3
8
16
8
16
20
8

34 39
1111100110000001101000011011100101
1100000100100011111000000110000100
1111111010111000010001001000000100
1001010101100000011011110011110000
1000110101101100100011000110010100
1101111001101100111111100101001110
0101000000001010001010110001101101
1110100010100100010001010101110001
0110110001000101110110000110000010
0111101111001011001110100011110010
1010010001100110000001111101010000
0110100100101001001001101011011101
1011110100010101011001100100110001
1010000111101000011111001101101000
1010101101110100100001111100011011
1110000000101111111110000111000010
0111000111000110101100111110011101
0011011101110001110101011111100100
1110001000000000010110111101111010
0101111001101000111100100111001000
0111101010111111110000010000110101
0101101101101000101111110010111011
1010100010111101101011100011101100
1100111111010100111001000000110011
0001101101100000111101101001100101
1111110011110001011001001110111001
1100010111000001101011101010101111
0000010100100011000011101100010010
0010000010010010001000001011111000
0001111000011000110101000001101010
0011110000100110000110111010001101
0001010010001010010110011011001110
0110111000010110000110001000111110
1100110111001110000101111110111010
21 12
18 20
11 28
13 13
10 11
33 17
3 22
20 20
26 14
16 18
29 33
12 30
15 25
12 14
14 31
34 3
20 15
7 1
28 17
4 6
20 1
23 6
31 20
31 2
19 29
20 29
27 24
13 11
5 4
29 2
4 2
24 3
25 5
1 18
4 30
19 7
15 24
15 23
15 12

147
147
90
147
4
1
22
147
1
147
90
14
4
147
90
24
3
147
147
33
73
73
2
24
5
5
147
147
33
24
3
73
73
5
3
73
90
147
147

说明/提示

对于样例，所有格子互相可达。

• 对于 $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$。