```
Time Limit: 4000 MS    Memory Limit: 65536 K

Description

The city of Stockholm is a chessboard whose size is N*M.
There are some Stockholm Knights in the city.
Stockholm Knights are very special Knights.
They only can move from a corner of a 3*4 grid to the opposite.
For example, Stockholm Knights can move from (10,10) to
(12,13) (12,7) (8,13) (8,7) (13,12) (7,12) (13,8) (7,8).

There are some destinations in the city.
And some grids of the city are destroyed
which Stockholm Knights cannot step into.

Every day, each knight can stay up,
or choose to move to another position.
Note that two knights cannot appear in the same grid on the same day.
Can you tell me the minimal days needed to
make all destinations be occupied by Stockholm Knights?

Input

The first line of input is the number of test case.
For each test case:
The first line contains three integers N, M.
The next N lines each contains M characters.

"*" represents free grid.
"#" for destroyed grid.
"D" for destination.
"K" for Stockholm Knight.

There is a blank line before each test case.

1<= N,M <= 30

Output

For each test case output the answer on a single line:
If you can make all destinations be occupied by Stockholm Knights
less than 30 days, output the minimal days.
Otherwise, just output ">30".

Sample Input

7

5 7
######D
#######
###D###
#######
K#####K

3 4
###D
####
K###

3 7
###*###
#######
K#####D

5 7
K#####D
#######
###*###
#######
K#####D

3 4
****
****
***K

3 4
****
****
***D

10 10
#D#KKK#**K
**###*KD##
KK#****##K
*D####K###
##D#*####*
#*D##*#*K#
#DKD##D###
#K#K#**D##
##K###**#*
#*DK###K##

Sample Output

2
1
2
3
0
>30
8

Source

8th SCUPC

Author

windy7926778

```