年僅5歲的阿峻已是一名高中生。他在2歲時就會背九九乘法表，3歲時就已經會多項式，4歲就會微積分，因而得到了「天才」的封號。不過，他最近卻遭遇到了人生的第一個挫折。

阿峻迷上了一個有趣的益智遊戲，這個遊戲是這樣的：有一個長、寬、高為1*1*2的方塊，從起始點開始上下左右移動它，想盡各種方法避開所有障礙，使方塊「垂直」立在終點就贏了！

範例走法

阻礙(#)

阻礙(o)

測資第一行為一整數T，表示接下來有幾組輸入。

每組輸入第一行為二整數m,n(m,n<=20)，分別表示幾行、幾列。

接下來為一個m行n列的地圖。S 代表木塊起始點， E 表示終點， # 表示該處為不可碰觸的障礙， o 表示不能「直立」在該點， . 代表該處為沒有任何阻礙的安全點。

請參考範例輸入

如果該測資無解，則輸出”NA”。

如果有解，則輸出包含三行。第一行輸出最少步數；第二行輸出「轉換方向」的次數；第三行輸出走法，以^ v < > 分別代表上、下、左、右，如果出現連續相同方向的話，請以 “走法 x 次數” 表示。

請參考範例輸出

3

5 5
#####
#...E
#.###
#.###
#S###

5 5
#####
.o..E
..###
..###
S.###

6 10
...#######
.S....####
.........#
#.........
#####..E..
######...#

min: 4
turns: 1
^x2 >x2

NA

min: 7
turns: 3
>x2 v >x3 v

測資有誤的話請通知~

感謝david942j幫忙測試數據!