Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4015
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


Author: LIN, Xi
Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status