**Problem Description**

Now the baker has made a piece of N*M cake with both chocolate and cream. Alice prefers cream but bob prefers chocolate. In order to make both of them happy, the baker decided to divide the cake into pieces that completely separate chocolate and cream, in other words, each piece is either chocolate or cream. Each operation the baker will choose a piece of cake (this cake could be created by the previous operation，one cut can’t operate on multiple pieces) and cut it along one of the vertical or horizontal axes. The bake wants to know the least cut he can be used to completely split the cake.

**Input**

Input contains an Integer T in the first line, represents the number of cases.

For each case, the first line contains two Integers N, M, represents the size of cake. Following N lines, each line contains a string with M characters, represents the details of cake.

‘x’ means chocolate, and ‘o’ means cream.

Limit:

T <= 10

N, M <= 40

**Output**

For each case output one line contains an Integer represents the least cut.

**Sample Input**

1 4 4 xxoo xxoo xooo xoxx

**Sample Output**

4

**Hint**

xxoo x|xoo x|x|oo x|x|oo x|x|oo

xxoo x|xoo x|x|oo x|x|oo x|x|oo

xooo => x|ooo => x|o|oo => x|-|oo => x|-|oo

xoxx x|oxx x|o|xx x|o|xx x|o|--

o o|xx

the ‘-’ and ‘|’ represent the position of cut. Total 4 cuts.

**Source**

2019绍兴市计算机技能竞赛