题目描述

华强来水果摊买西瓜。

现在水果摊老板有个lXl 的正方形字母矩阵代表每个西瓜，现在他想进行q 次询问，每次询问最长的以(xi,yi) 为中心的在一条水平或竖直的直线上的回文串的长度。

输入格式

第一行输入两个整数l,q ，分别表示矩阵的边长和询问的个数。

接下来的l 行，每行l 个字母，表示这个矩阵上的字母。 接下来的q 行，每行两个整数xi,yi ，表示第i 个询问为在询问矩阵中最长的以(xi,yi) 为中心的在一条直线上的回文串的长度。

输出格式

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

样例 #1

样例输入 #1

5 5
abcba
bcdcb
cdedc
bcdcb
abcba
1 1
1 2
1 3
2 3
3 3

样例输出 #1

1
1
5
5
5

提示

对于100% 的数据，1<=l,q<=2000 ，字母矩阵中不一定只有小写字母，但保证只有可见字符。

样例解释：

对于第一组询问，答案为 a。

对于第二组询问，答案为 b。

对于第三组询问，答案为 abcba。

对于第四组询问，答案为 bcdcb。

对于第五组询问，答案为 cdedc。