It's holiday season. A mall is empty except of air, money, and a very clever thief that is you.
The mall consists of n floors. Each floor can be represented as a rectangular 2D grid. All floors have the same 2D dimensions. You are somewhere inside the building. Your job, as a hard-working thief, is to collect c coins and then run to freedom through the exit door at the northwest corner cell of the first floor, in the minimum number of steps.
Each cell is either empty, a wall, a magic cell, or has a coin. You can move in the 4 compass directions as long as the cell you're moving to is not a wall. Moving from a cell to an adjacent cell takes 1 step. A magic cell can take you from the cell it's on to the corresponding one in another fixed floor (unless it's a wall), for no extra steps (other than the step you took to go to it). You can use it several times. Note that you can use the magic cell as an empty cell.
Floor representation: rectangular 2D grid of cells. Each cell contains a symbol or a character:
'.' represents an empty cell. '!' represents your start position. 'S' represents a coin which you can take or ignore by passing through this cell. After a coin is taken, you can't retake it by moving through the cell again. '*' represents a wall which you can't pass. a character between indicating this is a magic cell, and the character represents the floor the magic cell can take you to. First floor is a, second is b, .. etc. Input The input file consists of t (1 ≤ t ≤ 1024) test cases. The first line of each test case contains n, x, y (1 ≤ n, x, y ≤ 20) and c (0 ≤ c ≤ 8) - the number of floors, the dimensions of any floor, and the number of coins.
n grids follow, the ith grid represents the ith floor. For every grid you will read x lines, each contains y cells.
The total number of coins will not exceed 8.
Output If you can't collect the c coins and run away print -1 otherwise print the minimum number of steps needed to complete your mission.
7 1 1 1 0 ! 2 1 3 1 .!b .aS 2 1 4 1 .!.b .aSS 2 1 4 1 .!.b ..SS 2 1 4 2 .!.b Sa.S 2 1 4 2 .!.b .a.S 2 1 4 2 S!.b .a.S
0 3 5 -1 7 -1 5
Note If we model each floor as a matrix indexed from (0, 0) to (x - 1, y - 1):
To run away, you'd need to go cell (0, 0) in the first floor.
A magic cell called 'e' on, for example, the 3rd floor in cell (2, 4) could take you to cell (2, 4) (unless it's a wall) on the 5th floor for no extra steps.