시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB247729.167%

문제

You are given a rectangular grid of $M$ rows and $N$ columns. The rows and columns are indexed from $0$ to $M - 1$ and from $0$ to $N - 1$ respectively. In each grid cell $(i, j)$, there is a lowercase letter character $A[i, j]$. This grid represents a maze, and the goal to solve the maze is to find a walk going from $(0, 0)$ to $(M - 1, N - 1)$. The walk consists of several steps. In each step you can choose one of the four directions (going from a grid cell to a neighboring cell that shares an edge.) Notice that it is okay to revisit a cell multiple times during the walk, including the starting cell $(0, 0)$ and the ending cell $(M - 1, N - 1)$. If you record all characters along the walk, you’ll get a string that represents this walk.

Truckski is not a fan of palindromes, so he would like to find a walk that does not contain any palindromic substrings of length at least two, which he called a good walk. A string $s_1s_2 \cdots s_k$ is called a palindrome, if it reads the same after reversing the string, i.e., $s_1s_2 \cdots s_k = s_ks_{k-1} \cdots s_1$. A substring of a string can be obtained by removing a (possibly empty) prefix and a (possibly empty) suffix.

Now, there are $Q$ interesting locations $\{(r_i , c_i)\}^Q_{i=1}$ that Truckski wishes to visit. For each location $(r_i , c_i)$, can you help Truckski to find the length of the longest good walk that visits the location grid cell $(r_i , c_i)$ at least once? If there are arbitrarily long good walks please output $-1$. If there does not exist any good walk, please output $-2$.

입력

The first line contains an integer $T$, indicating the number of test cases. For each test case, there are two integers $M$ and $N$ in the first line. In each of the following $M$ lines there is a string of length $N$, the $c$-th character in the $r$-th line is the character $A[r, c]$. The next line contains an integer $Q$. In each of the following $Q$ lines there are two integers $r_i$ and $c_i$ indicating the location of interest.

출력

For each interesting location, output the length of the longest good walk that visits this location at least once, or $-1$ if the good walk can be arbitrarily long, or $-2$ if there does not exist such a good walk.

제한

  • $T ≤ 20$
  • $2 ≤ M ≤ 100$
  • $2 ≤ N ≤ 100$
  • $1 ≤ Q ≤ 100$
  • For all $i$ such that $1 ≤ i ≤ Q$, $0 ≤ r_i < M$ and $0 ≤ c_i < N$.
  • For each grid cell $(r, c)$, $A[r, c] ∈ \{$a, b, ... , z$\}$ is a lowercase letter.

예제 입력 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

노트

This problem is not the easiest problem in this contest.