Longest Distinct Character Path in a Matrix

Given a matrix of characters, find the length of the longest path such that all characters in the path are distinct.

You may move in eight directions (horizontally, vertically, or diagonally). The path can start at any cell, and each cell may be visited at most once per path with respect to its character value.

More formally, in a matrix \( A \) of size \( N \times M \), determine the maximum length \( L \) of a path \( (i_1, j_1), (i_2, j_2), \ldots, (i_L, j_L) \) that satisfies:

• \( |i_a - i_{a+1}| \le 1 \) and \( |j_a - j_{a+1}| \le 1 \) for \( 1 \le a < L \), and
• \( A[i_a][j_a] \neq A[i_b][j_b] \) for all \( a \neq b \).

Your task is to implement an algorithm to compute this longest path length.

inputFormat

The input is read from standard input in the following format:

T
N M
row_1
row_2
... 
row_N
[repeat for T test cases]

Here, \( T \) denotes the number of test cases. For each test case, the first line contains two integers \( N \) and \( M \), representing the number of rows and columns of the matrix, respectively. Each of the following \( N \) lines contains a string of length \( M \) representing a row of the matrix. Note that if \( M = 0 \), then the corresponding row will be an empty string.

outputFormat

For each test case, output a single integer representing the length of the longest path with distinct characters, printed on a separate line to standard output.

## sample

5
3 4
abcd
efgh
ijkl
2 2
aa
bc
2 2
ab
ca
1 1
a
1 0

12
3
3
1
0

</p>