Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
152 - The 18th Zhejiang University Programming Contest Sponsored by TuSimple - B
Liblume

Time Limit: 4 Seconds      Memory Limit: 262144 KB

DreamGrid has a matrix \(A\) consisting of lowercase English letters. You are allowed to rearrange its rows any number of times (including zero times). Please calculate the maximum possible area of a submatrix in which every row and column is a palindromic string after the rearrangements.

Let's assume that the rows of matrix \(A\) are numbered from \(1\) to \(n\) from top to bottom and the columns are numbered from \(1\) to \(m\) from left to right. A matrix cell on the intersection of the \(i\)-th row and the \(j\)-th column can be represented as (\(i, j\)).

A palindromic string is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A submatrix of matrix \(A\) is a group of four integers \(d, u, l, r\) (\(1 \le d \le u \le n, 1 \le l \le r \le m\)). The submatrix contains all the cells (\(i, j\)) satisfying both \(d \le i \le u\) and \(l \le j \le r\). The area of the submatrix is the number of cells it contains.

Input

There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n \times m \le 2 \times 10^5\)) -- the number of rows and columns of the matrix.

Each of the next \(n\) lines contains \(m\) characters denoting the matrix.

It is guaranteed that the sum of \(n \times m\) in all cases does not exceed \(2 \times 10^6\).

Output

For each test case, output an integer denoting the maximum possible area of a submatrix in which every row and column is a palindromic string after the rearrangements.

Sample Input

4
2 2
aa
aa
3 3
aaa
aaa
bbb
3 3
abc
def
ghi
3 3
aba
bab
aba

Sample Output

4
9
1
9

Submit    Status