ISLAND_ATTACK - Island Under Attack!


Once upon a time, there were villagers who lived happily in Martian archipelago . Suddenly, Chris to van Necrophos , the most notorious wizard from the Offense of the Ancients , suddenly came there and started a havoc. At first, he started to use his spell to steal the life power of others. Luckily, there were some shelters that can protect the villagers from that spell, and there was still enough time for all of the villagers to go to any of the shelters available. Yet, the shelters were only able to hold some villagers. The wizard also created dark barriers in each islands so that every villagers could not escape from their islands. The magician also had a special ability that, if the numbers of the villagers that he had consumed in an island was more than half of the island's population, the whole island would be destroyed and consumed by the magician instead, including the shelters and the villagers inside.

Now, you are given a map of the place where Chris to attack. You need to determine how many people in all of those island would survive after the attack. the map will be in a size of N × M. The villagers will be denoted as "H". The shelters will be denoted by a number from 1-9, which is the number of villagers that can get inside the shelters. The sea water is denoted as "." and the land is denoted as "#".

The area of lands is considered as the same island as long that the land is adjacent with any other entities except the sea water.

The area outside the provided map is considered as open sea, so they couldn't go out of the provided map.

Note: See input examples for clarification.

Input

Input starts with an integer T (1 ≤ T ≤ 20), denoting the number of test cases. Each of the test cases consists of integer N and M (1 ≤ N, M ≤ 100), denoting the size of width and length of the map. After that, each testcases will have N more lines, which is the map at that time.

Output

For each case print "Case #X: There are P survivors.", where X (1 ≤ X ≤ T) is the case number and P is the total number of villagers that could survive from that assault. If there are no survivors, then print "Case #X: There is no survivor.". If there is exactly one survivor, print "Case #X: There is 1 survivor." instead. There must be no trailing spaces at the end of printed lines, neither empty characters. Print a newline after each testcase.

Example

Input:
1
4 7
....##.
#H3HH#.
H#.#H#.
......#

Output:
Case #1: There are 3 survivors.

hide comments
rapiram31: 2022-11-26 08:49:43

Stupid problem, cannot find why am getting Wa:(
Can someone clarify this - if there are n people in an island and m people can go into shelters
if (2 * (n - m) > n)then magician will destroy the entire island
else survivors += n - max(0,(n - m))

Last edit: 2022-11-26 08:50:10
codingjedi048: 2021-09-22 12:02:24

""The magician also had a special ability that, if the numbers of the villagers that he had consumed in an island was more than half of the island's population, the whole island would be destroyed and consumed by the magician instead, including the shelters and the villagers inside.""

--- Do not forget this fact.

code_ster: 2019-04-21 00:50:16

@hastananda can you please check my submission, Can you point out, what I am missing in my submission?

hodobox: 2016-11-22 09:40:27

My assert on r,c>0 is failing

avisheksanvas: 2016-07-15 13:43:25

@hanstananda Please check my submission. Why am I getting WA?


Added by:hanstan
Date:2016-05-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Self