Dungeon Escape in a 3D Prison

You are participating in a secret mission and have been trapped in a 3D underground prison. The dungeon consists of several layers, each of which is a square grid of size N×N. Each cell in the grid is either passable or blocked by rock. There is exactly one starting cell marked with S and one exit cell marked with E in the entire dungeon. From any passable cell, you can move to the cell in front, behind, to the left, right, in the upper layer, or in the lower layer, if that cell exists and is not blocked. Moving to an adjacent cell takes 1 minute. Your task is to determine whether it is possible to escape from the dungeon, and if so, find the minimum time (in minutes) required to reach the exit.

The movement can be summarized by the following six directions:

[ \begin{array}{l} \text{Up (layer+1): } (l+1, r, c) \ \text{Down (layer-1): } (l-1, r, c) \ \text{North: } (l, r-1, c) \ \text{South: } (l, r+1, c) \ \text{West: } (l, r, c-1) \ \text{East: } (l, r, c+1) \end{array} ]

If escape is possible, output the minimum time in minutes; otherwise, output -1.

inputFormat

The input begins with an integer T (T ≥ 1) indicating the number of test cases. Each test case starts with a line containing two integers: L and N, where L (L ≥ 1) is the number of layers and N (N ≥ 1) is the size of each square layer. This is followed by L blocks, each representing one layer. Each block consists of N lines, and each line contains exactly N characters. The characters can be:

• S for the starting cell (appears exactly once per test case),
• E for the exit cell (appears exactly once per test case),
• . for a passable cell,
• # for a blocked cell (rock).

Note: There are no blank lines between layers.

outputFormat

For each test case, output a single line containing the minimum number of minutes required to escape the dungeon. If escape is impossible, output -1.

sample

3
3 3
S..
.##
...
##.
...
.##
...
.##
..E

5