该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

做为老柿子在每个情人节必直播的游戏，已经成为每年必看的节目之一。这一天水娃和火娃俩兄弟在字符森林里迷路了，当他们两个人正在一个十字路口徘徊时，老柿子告诉他们，这两条路的权重不一样，你们只需要选权重最大的一条路走就可以了。对于权重就是这条路上以当前位置为中心，所有字符所构成回文字符串的最大长度。目前只有垂直和水平两条路供他们选择，聪明的OIer请帮助他们选择一条正确的道路吧！

输入格式

第一行输入两个整数 $n,m$ 代表这片森林有 $n$ 行 $n$ 列。

接下来的 $n$ 行,每行 $n$ 个字母，表示这片森林中字符。

接下来的 $m$ 行，每行两个整数 $x_{i},y_{i}$，表示第 $i$ 个询问为在所处的这片森林中以当前位置$(x_{i},y_{i})$为中心，在当前位置垂直和水平两条路上最大的权值。

输出格式

输出 $m$ 行，第 $i$ 行为对于第 $i$ 个询问的回答。

样例

输入1

5 3
zxzvb
zwzwz
wwwww
zwzwz
abcba
1 1
1 2
2 3

输出1

1
3
5

提示说明

对于 $20\%$ 的数据，$1 \le m\le 2$

另有 $20\%$ 的数据，$q=1$

另有 $20\%$ 的数据，字符森林完全对称即中心、上下、左右和对角线都对称。

对于 $100\%$ 的数据，$1\le n,m\le 2000$ 保证字符只有小写英文字母。