Ronny is hiding on the building where he left his family after failing the guard test (the guard told him not to cheat and got angry after your help). The Rainbowlandians are brutally attacking the citizens of planet Earth, there are corpses everywhere and desperate people running on the street. Ronny must protect his family and that’s why he has decided to take down all the Rainbowlandians inside the building as soon as possible.

Ronny know very little about the Rainbowlandians, but he knows that he must be silent when he takes down one of then, hence, he hides his noisy gun in his pocket, impeding him to attack them from the distance. In order to take down the Rainbowlandians, a knife or a good flying kick will do the job. Ronny must step on the same space a Rainbowlandian is to take him down. The building is full of rubble and some paths will lead to a trap. Fortunately, Ronnie can throw a rope and go up or down through floors while he is walking the building. Obviously, he cannot throw the rope if this will lead him to a rubble-full step.

Given the dimensions of the building, its width, height and depth and the marked targets, you’re to make a program to help Ronny take down the Rainbowlandians in the minimum steps possible so he can do the minimum noise possible.

Please note that:

• Ronny starts at the north west corner of the first floor of the building (1,1,1)
• Ronny can only move to these possible directions: east, west, north, south, in addition, he can go while moving up or down.
• Ronny cannot leave the building at any moment and there’s no basement in the building neither, so he can’t be lower than height 1.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case will start with two integers N and H, where N denotes the width and depth of each floor and H denotes the number of floors. Then, there will be H N×N matrices, each one describing one floor. The floor description is composed of the following characters:

• The character ’#’ denotes a rubble space.
• The character ’.’ denotes a free space.
• The character ’*’ denotes a Rainbowlandian.

Output

For each input case you must print the string "Scenario #i: " where i is the test case you’re evaluating (starting at 1), followed by the minimum steps that Ronny have to make to take down all the enemies inside the building. If this is impossible, print -1.

Sample

Input
3
2 1
..
.*
3 2
.#.
.##
##.
#.#
###
.#*
4 3
....
.##.
####
****
####
####
....
#.##
####
*..*
*..*
####

Output
Scenario #1: 2
Scenario #2: -1
Scenario #3: 13

Constraints

• 1 ≤ T ≤ 30
• 1 ≤ N ≤ 20
• 1 ≤ H ≤ 20
• 1 ≤ Targets ≤ 10