时间限制： 1.0 秒

空间限制： 512 MB

题目描述

Bloxorz 是一款风靡全球的益智游戏，以其独特的方块操控和复杂的关卡设计而著称。在这个游戏中，玩家需要使用键盘方向键来控制方块的移动，使其到达指定的终点。

具体的游戏规则如下：给定一个平面网格区域，每一格为空地，地面或玻璃。在地面上放置着一块 $1\times 1\times 2$ 的长方体木块，可以竖放在一格地面上，或平放在相邻的两格地面、或相邻的两格玻璃、或相邻的一格地面和一格玻璃上。每次操作可以选择四个方向中的一个，将木块向该方向滚动 $90\degree$。游戏的目标是以最少的移动次数将盒子竖放在唯一的目标地砖上。初始位置和目标位置的区域类型均为地面，而非玻璃或者空地。

给定一个 $n\times m$ 的平面网格，其中 # 表示空地，. 表示地面，E 表示玻璃，X 表示初始位置，O 表示目标位置，求达成游戏目标的最小操作数。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

输入的第一行包含两个正整数 $n,m$，表示平面网格的大小。

输入的第 $i+1~(1\le i\le n)$ 行包含一个长度为 $m$ 的仅由 #、.、E、X、O 组成的字符串，描述给定的游戏局面，具体含义如【题目描述】中所示。

输出格式

输出到标准输出。

对于每组测试数据：

输出一行一个整数表示到达成游戏目标的最小操作数。特别地，若游戏目标无法达成，则输出 $-1$。

1
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######

10

子任务

对于所有测试数据，保证 $1\le T\le 5,~3\le n,m\le 500$，保证每个游戏局面都有恰好一个 O 与恰好一个 X 或相邻的两个 X。保证给定的游戏局面中的第一行、第一列、最后一行、最后一列均为 #。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。