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

中心同色广场

题目背景

在圣彗星兰的实验室里，噜噜正在观察一块由小格子组成的字符地毯。每个格子上都写着一个小写字母。她站在地毯上的某个格点 $(r, c)$，想知道：以这个点为正方形中心（两条对角线交点），能铺出的、全部字符相同的最大正方形边长是多少？

注意：正方形的中心必须落在格点中心，因此合法的边长一定是奇数（1、3、5、…）。

题目描述

给定一个 $M \times N$ 的字符网格（行数为 $M$，列数为 $N$），左上角坐标为 $(0,0)$，右下角坐标为 $(M-1, N-1)$。 对每个询问位置 $(r, c)$，请你求出：以 $(r, c)$ 为中心，且正方形内所有字符相同的最大正方形的边长。

示例中，给定位置 $(1,2)$ 时，答案为 3。

abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa

输入格式

• 第一行是一个整数 $T < 21$，表示测试用例数量。
• 每个测试用例包含：
  1. 一行三个整数 $M, N, Q (< 21)$，表示网格的高、宽和询问个数。
  2. 接下来 $M$ 行，每行 $N$ 个字符，构成网格。
  3. 接下来 $Q$ 行，每行两个整数 $r, c$，表示一次询问的位置。
• 约束：$M, N \le 100$。

输出格式

对每个测试用例输出共 $Q+1$ 行：

• 第一行输出该用例的 $M, N, Q$（以空格分隔）。
• 之后的 $Q$ 行中，每行输出对应询问的最大同色正方形边长。

样例输入

1
7 10 4
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
1 2
2 4
4 6
5 2

样例输出

7 10 4
3
1
5
1

说明与提示

• 正方形需完全落在网格内，中心固定为 $(r, c)$。
• 所求边长为奇数，最小为 1（只取中心单格）。