MONKK - Monkey King

no tags 

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

hide comments
nadstratosfer: 2019-07-09 07:23:00

I'm convinced there's something wrong with the input. I kept getting WA with Python but got AC with same algo in C where I was able to use some more idiot-proof reading.

Vivek Mangal: 2016-04-03 22:20:14

Passed all the cases on spoj toolkit but spoj is showing WA.
id=16663879.Any special case?
Finally accepted.I was using 2d char array but now used array of type string.

Last edit: 2016-04-05 17:05:08
Baojun Wang: 2016-03-02 03:08:09

1) rows or cols can be 0 (contradict the statement);
2) For below case:
1
1 1
T

return 0 instead of -1.

manish kumar: 2015-08-20 22:43:57

please help..don't know why getting wrong answer
http://www.spoj.com/submit/MONKK/id=14940412

Harish Reddy Kolanu: 2015-08-15 12:53:29

Simple Brute force solution works :P

Shivaraj Lakka: 2015-07-18 19:14:32

by checking all squares its TLE! plz hint...

Akash Goel: 2015-07-13 15:33:49

Getting WA.
http://www.spoj.com/submit/MONKK/id=14659974

Priyanjit Dey: 2015-07-06 20:36:41

Anyone plz provide any tricky cases... getting wa. I dont know why. I am pretty much sure about the algo i used.

Never mind.. solved it.

Last edit: 2015-07-07 07:21:05
ag_shar96: 2015-06-29 01:15:01

By checking every square m getting TLE is their any faster approach????
RE: Finally AC time 0.18 can it be reduced???

Last edit: 2015-06-30 02:03:00
gamer496: 2015-06-26 12:15:58

@admin could you tell what's wrong with solution submission_id 14541100
Any corner case??

Last edit: 2015-06-26 12:49:38

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