2270: Minimum coverage matrix

Give you a character matrix, you need to find a sub matrix which can “cover” the whole matrix, and its size should be minimum. 

In addition, you must assure that the left-top element is in the sub matrix. For example:

ABCDEFAB

AAAABAAA

ABCDEFAB

We can find the following minimum coverage matrix:

ABCDEF

AAAABA

Because by extension we can get:

ABCDEFABCDEF

AAAABAAAAABA

ABCDEFABCDEF

AAAABAAAAABA

We see it contains the original matrix.

First line contains a integer T(1<=T<=30), indicating the case count.

For each case, first line contains two integers R(1<=R<=500) and C(1<=C<=500), 

seperated by a space, there will be a R*C character matrix next.

The size of minimum coverage matrix in a line.

3
3 8
ABCDEFAB
AAAABAAA
ABCDEFAB
2 8
ABCDEFAB
AAAABAAA
1 1
A

12
12
1