MONKK - Monkey King

There is a king name Monkey. He love bananas so much. In his kingdom there is big field which contains many banana trees. We can represent this field as a 2D grid. In this grid some of the cells are contains banana tree, some of them are empty and some of the cells are are for tax area. If you select a cell which contains a banana tree then you can earn a banana and if you select a cell which is tax area then you must pay a banana to Monkey King. 

Monkey king is really an intelligent man like a monkey. Today he gets an excellent idea. He wants to give you a chance to earn some bananas. But there is a condition for that. That condition is you can select only a square area from this field (2D grid).

Now Monkey King wants to know how many bananas (as much as possible) you can earn from this field.

Input

Input starts with an integer T (<= 213), denoting the number of test cases.

Each case starts with a line containing two integers r and c (0 <= r, c <= 100), r denotes the number of rows and c denotes the number of columns of the modelled grid. Each of the next r lines contains c characters representing the field.

You can assume that there will only three kinds of charter and those are ‘B’, ‘.’ and ‘T’. ‘B’ for banana tree, ‘.’ For empty and ‘T’ for tax area.

Output

For each case print the case number and the maximum number of banana you can earn.

Example

Input:
2

3 3
BBB
BBB
BBB

5 5
T.BBB
TBBBB
.BBBB
TBBBB
.BBBB

Output:
Case 1: 9
Case 2: 16

Added by:shuvo karmakar
Date:2015-06-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-06-23 01:29:39 Soma
@bruceleefinal: there are 19 banana trees in the 5x5 field and 3 tax areas so 19-3=16 and remaining 3 are empty areas which are not included (4x4 also yields 16).
2015-06-22 21:33:34
I'm an idiot

Last edit: 2015-06-23 06:47:09
2015-06-22 10:31:03 jitendra
PLEASE HELP.. DON'T KNOW WHY getting wrong answer.. running in visual studio 13 c++
http://www.spoj.com/submit/MONKK/id=14511315
2015-06-22 09:17:50 Bruce Wayne
O(r*c) is sufficient.
2015-06-22 09:04:41 :.Mohib.:
Any hint plzz....I am getting tle... :(
2015-06-21 15:58:40 SRC
Should be squares only !

Last edit: 2015-06-21 16:03:14
2015-06-21 10:42:13 :.Mohib.:
We have to choose square area or we can choose rectangle also??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.