After the collision of the great Titanic with the iceberg, it went down. Now there are peoples floating in the cold water struggling with death. Some helping ship will arrive to save them. But they have to survive until the ships arrive. Now consider a water area with people, floating ices, large woods etc. Consider the following symbols:
Given the description of the area you have to find an optimal strategy that ensures the maximum number of living people. Input The input contains a number of test cases. Each test case starts with a line containing three integers X,Y andP,whereX,Y isthedimensionsofthearea(1≤X,Y ≤30)andP (P ≤10)isthehighest capacity of the large woods. Next X lines each contains Y characters. These lines contain no blank spaces or any characters other than asterisk (*), tilde (~), dot (.), at (@) and hash (#). Not more than 50% of the total area has a people. Input will terminate with end of file (EOF). There is a blank line between two consecutive test cases. Output For each test case print one line of output, an integer denoting the maximum number of survivors possible. Sample Input 342 ~~# ...@ .~.
2/2
351 * #.@.# *
142 **#~
Sample Output
2 2 1