给定一个 $M$ 行 $N$ 列的矩形网格。行和列的索引分别从 $0$ 到 $M-1$ 和 $0$ 到 $N-1$。每个网格单元 $(i, j)$ 中都有一个小写字母 $A[i, j]$。该网格代表一个迷宫，目标是找到一条从 $(0, 0)$ 到 $(M-1, N-1)$ 的路径。路径由若干步组成。每一步，你可以选择四个方向之一（从当前单元格移动到共享边的相邻单元格）。注意，在路径中可以多次访问同一个单元格，包括起点 $(0, 0)$ 和终点 $(M-1, N-1)$。如果你记录下路径上的所有字符，就会得到一个表示该路径的字符串。

Truckski 不喜欢回文，因此他想找到一条不包含任何长度至少为 $2$ 的回文子串的路径，他称之为“好路径”。如果一个字符串 $s_1s_2 \dots s_k$ 在反转后与原字符串相同，即 $s_1s_2 \dots s_k = s_k s_{k-1} \dots s_1$，则称其为回文。字符串的子串可以通过删除（可能为空的）前缀和（可能为空的）后缀得到。

现在，有 $Q$ 个 Truckski 希望访问的有趣位置 $\{(r_i, c_i)\}_{i=1}^Q$。对于每个位置 $(r_i, c_i)$，你能否帮助 Truckski 找到访问过该网格单元 $(r_i, c_i)$ 至少一次的最长好路径的长度？如果存在任意长度的好路径，请输出 $-1$。如果不存在任何好路径，请输出 $-2$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，第一行包含两个整数 $M$ 和 $N$。接下来的 $M$ 行中，每行包含一个长度为 $N$ 的字符串，第 $r$ 行的第 $c$ 个字符即为 $A[r, c]$。下一行包含一个整数 $Q$。接下来的 $Q$ 行中，每行包含两个整数 $r_i$ 和 $c_i$，表示感兴趣的位置。

输出格式

对于每个感兴趣的位置，输出访问过该位置至少一次的最长好路径的长度；如果好路径可以任意长，则输出 $-1$；如果不存在这样的好路径，则输出 $-2$。

数据范围

• $T \le 20$
• $2 \le M \le 100$
• $2 \le N \le 100$
• $1 \le Q \le 100$
• 对于所有 $1 \le i \le Q$，$0 \le r_i < M$ 且 $0 \le c_i < N$
• 对于每个网格单元 $(r, c)$，$A[r, c] \in \{\text{'a', 'b', \dots, 'z'}\}$ 为小写字母

样例

输入 1

3
3 5
abbba
bccab
cabcc
2
0 1
1 0
3 4
aaba
bbaa
abab
1
1 1
4 4
abca
cxxb
bxxc
acba
1
0 1

输出 1

9
9
-2
-1

说明

本题不是本次比赛中最简单的题目。