DWITE, October 2012, Problem 5

Let's get one thing straight: Halloween is all about the candy. And Little Billy is determined to get all of it. However, one of the neighbours seems to have had the same idea. They constructed a Haunted House to hide all of their candy so that only the truly worthy can get them. Little Billy managed to get his hands on the floor plan of the house, and realized that this was no ordinary haunted house: it seems to be full of fake walls. Being his only imaginary friend who can program, help Little Billy get as much candy as possible as quickly as possible.

The input will contain 5 test cases. The first line of each test case is an integer ~N~ where ~3 \le N \le 10~, the number of rows and columns in the floor plan, followed by ~N~ lines (each ~N~ characters long), describing the floor plan.

• . - empty space
• # - impassable wall
• B - Billy's start location
• * - piece of candy
• a-f - fake walls

Fake walls are unlockable only if Billy has already collected at least as much pieces of candy as the order of the letter. That is, door a requires at least ~1~ piece of candy. b ~= 2~. f ~= 6~.

The output will contain 5 lines of output, each a pair of non-negative integers ~C~ and ~S~. ~C~ is the maximum number of candy pieces that Billy can collect. ~S~ is the minimum number of steps to do so.

Sample Input

3
B.*
##b
..*
5
B...*
####a
.**..
#c#..
#*#..

Sample Output

1 2
4 11

Problem Resource: DWITE