TILING - Rectangle Tiling

no tags 

We say that a 2-dimensional, rectangular word w of size n×m (imagine it as a board with letter written in the squares) can be tiled with a rectangular pattern p if there are such occurrences of p in w (but not necessarily all of them) that no two of them overlap and each symbol (square) of w is covered by one of them. Given such word w, find a rectangular pattern p of smallest size (area) which the word w can be tiled with.

Input

The first line of input contains a number t (1≤t≤100) that indicates the number of test cases to follow. Each test case begins with a line consisting of two positive integers n and m (1≤n,m≤1000) indicating dimensions of the board. n lines follow, each of them containing m small letters of the English alphabet (a,b,...,z).

Output

For each test case output the smallest possible area of a pattern p that can be used to tile the given board.

Example

Input:
3
4 3
aaa
aaa
aaa
aaa
4 4
abab
cdcd
abab
cdcd
3 4
aaaa
aaaa
aaab

Output:
1
4
12


hide comments
lokesh gopu: 2014-08-03 11:28:33

@ymGXX : 12

Xiaotao: 2013-05-08 08:09:19

3 4
abca
abcb
abcc

Which is the answer of this case, 3 or 16?

ymGXX: 2013-05-08 08:09:19

3 4
abca
abcb
abcc

Ravi Kiran: 2013-05-08 08:09:19

Get a very good runtime using gets()!


Added by:gawry
Date:2007-11-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6