acmASCIS has a lot of diamonds under the ground of the faculty of computer and information science Ain Shams university "FCIS ASU". We have a map for all the diamonds. This map includes positions for diamonds, rocks and sand. Walking through the rocks isn't allowed. This map has only one path at most, In each cell you may have at most only one new cell that isn't a rock. We can move in the four directions (North, South, East and West) if it's possible. The full path must start from the label "FCIS ASU" and must end at the label "The center of the Earth" in the bottom right corner of the map. Mohamed is one of the members of acmASCIS, he wants to code a program that takes a map and tells him whether it's possible to reach the center of the Earth or not. If it's possible the program will calculate also the number of the steps and the diamonds from "FCIS ASU" to "The center of the Earth". Help Mohamed to code this program.

Notes:
It's only allowed to start from "FCIS ASU" to point (0,0) in one step.
"FCIS ASU" is up point (0,0) only.

Input

Your program will be tested on one or more test cases. The first line of input contains a single integer T (1<=T<=30) indicating the number of test cases. Each test case starts with a Number N (2<=N<=100), map size will be N*N. Followed by N lines each line has N symbols. One symbol S, (0<=S<=9, Number of diamonds), (S='#' for Rock), (S='.' for sand).

Output

For each test case, print "Case_#i:_X" where "i" is the number of the test case (starting with 1),
"X" is "Mohamed_can't_go_to_the_center_of_the_earth_:-(" or
"X" is "Mohamed_can_go_to_the_center_of_the_earth_:-)" followed by two lines Y and Z ,
Y="Number_of_steps_=_S" where "S" is number of steps from "FCIS ASU" to "the center of the earth " , Z="Number_of_diamonds_=_D" where "D" is the total number of all diamonds which Mohamed can get and "_" is a white space.

Example

Input:
4
6
1#####
1.1.1#
####.#
1.1.1#
.#####
1.1.1.
10
9#########
9#########
9#########
9#########
9999999999
#########9
1###999999
8###.#####
4###012345
.########6
4
####
9..8
###2
###9
10
###9######
1##9######
1##9######
1##9######
1##9######
1##9######
1##9######
1##99999##
1######11#
1111111##1


Output:
Case #1: Mohamed can go to the center of the earth :-)
Number of steps = 19
Number of diamonds = 10
Case #2: Mohamed can go to the center of the earth :-)
Number of steps = 29
Number of diamonds = 210
Case #3: Mohamed can't go to the center of the earth :-(
Case #4: Mohamed can't go to the center of the earth :-(