P4888 三去矩阵

无

现在小Y有个 $l \times l$ 的正方形字母矩阵，现在他想进行 $q$ 次询问，每次询问最长的以 $(x_i,y_i)$ 为中心的在一条水平或竖直的直线上的回文串的长度。

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

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

对于 $20\%$ 的数据，$1 \le l \le 2$。 另有 $20\%$ 的数据，$q = 1$。 另有 $20\%$ 的数据，字母矩阵中心对称，上下对称，左右对称且对角线对称。 对于 $100\%$ 的数据，$1 \le l,q \le 2000$，字母只有小写字母。