【题目描述】

给定一个 $n$ 行 $n$ 列的小写字母矩阵。

每次询问一个中心 $(x,y)$，求所有以该格为中心、位于同一行或同一列的回文串中，最长的长度。

【输入描述】

第一行输入两个整数 $n,m$。

接下来 $n$ 行输入字母矩阵。

接下来 $m$ 行输入询问坐标。

保证：

• $1\le n\le 1000$；
• $1\le m\le 10^5$；
• 矩阵只包含小写字母。

【输出描述】

输出 $m$ 行，每行一个整数。

【样例 1】

【样例 1 输入】

3 2
aba
bbb
aba
2 2
1 2

【样例 1 输出】

3
3

【样例 2】

【样例 2 输入】

4 1
abca
zzzz
abca
abca
2 2

【样例 2 输出】

3

【数据规模与约定】