A number of boxes is to be moved in a warehouse. The warehouse can be modeled as a grid where each square is the equal to the size of a box. Consider the model below: (‘B’ = box to be moved, ‘.’ = empty square, ‘X’ = position a box should occupy after the move, ‘#’ = obstacle) BBBB.... .###...X .XX#...X ...#.... ........ A box may be moved to any of its four neighboring squares, assuming this square is empty (that is, not occupied by another box or an obstacle). To move a box takes one unit of time, and only one box may be moved per time unit. Your task is to determine the least amount of time to move all boxes to their destination squares. You may assume that a solution exists. Number of boxes will be no more than 15. Input The first line in the input contains the number of test cases (at most 20). Each case starts with a line containing two integers, the height (1 ≤ h ≤ 40) and width (1 ≤ w ≤ 40) of the grid. Then follows h lines, each containing w characters, describing the grid in the format above. Output For each test case, output a line containing a single integer: the minimum number of time units to move all boxes. Sample Input 1 58 BBBB.... .###...X .XX#...X ...#.... ........ Sample Output 20