Problem Description
Mark bought a huge cake, because his friend ray_sun’s birthday is coming. Mark is worried about how to divide the cake since it’s so huge and ray_sun is so strange. Ray_sun is a nut, you can never imagine how strange he was, is, and going to be. He does not eat rice, moves like a cat, sleeps during work and plays games when the rest of the world are sleeping……It is not a surprise when he has some special requirements for the cake. A considering guy as Mark is, he will never let ray_sun down. However, he does have trouble fulfilling ray_sun’s wish this time; could you please give him a hand by solving the following problem for him?
The cake can be divided into n*m blocks. Each block is colored either in blue or red. Ray_sun will only eat a piece (consisting of several blocks) with special shape and color. First, the shape of the piece should be a rectangle. Second, the color of blocks in the piece should be the same or red-and-blue crisscross. The so called ‘red-and-blue crisscross’ is demonstrated in the following picture. Could you please help Mark to find out the piece with maximum perimeter that satisfies ray_sun’s requirements?
Input
The first line contains a single integer T (T <= 20), the number of test cases.
For each case, there are two given integers, n, m, (1 <= n, m <= 1000) denoting the dimension of the cake. Following the two integers, there is a n*m matrix where character B stands for blue, R red.
Output
For each test case, output the cased number in a format stated below, followed by the maximum perimeter you can find.
Sample Input
2
1 1
B
3 3
BBR
RBB
BBB
Sample Output
Case #1: 4
Case #2: 8
