Hero A（显然是一个化名）是超级共鸣心灵感应中心（SRPH）的申请者之一，这是一个由拥有心灵感应能力的超级英雄组成的杰出协会。在通过了第一轮考试后，他目前正在奥地利维也纳度假。
然而，当他意识到自己看错了期末考试的时间表时，这个假期很快就被打断了。考试并不是在他度假回来后举行……而是现在就要举行！
为了不想在余下的假期里反思自己被梦想拒之门外，他充分利用自己的能力，远程召唤了一个自己的克隆体来参加考试，并由他通过心灵感应进行控制。
考试要求申请者利用他们的心灵感应能力导航一个迷宫，该迷宫由一个 $r \times c$ 的网格（$r$ 行 $c$ 列）表示，我们称之为网格 B。Hero A 在奥地利找到了一个具有相同 $r \times c$ 网格形状的房间，并从这里参加考试；我们称之为网格 A。
Hero A 创建了一个克隆体（我们称之为克隆体 B），它出现在网格 B 的某个位置。每当 Hero A 移动时，克隆体 B 也会尝试模仿该动作（例如，如果 Hero A 向右走一步，克隆体 B 也会尝试向右走一步）。目标是让克隆体 B 在网格 B 设置的迷宫中导航并到达标记的终点。
不幸的是，这个设置并不完美。虽然可以保证网格 A 和网格 B 具有相同的 $r \times c$ 维度，但 Hero A 和克隆体 B 可能不会在网格的相同位置开始。此外，网格 A 和网格 B 都有障碍物，但这些障碍物可能放置在不同的位置！
具体来说，克隆体 B 的控制方式如下：
- Hero A 每次只能水平或垂直移动一步。
- Hero A 和克隆体 B 都不能走进障碍物，也不能走出网格。
- 当 Hero A 在给定方向上移动一步时，克隆体 B 将尝试在同一方向上移动一步。
- 如果克隆体 B 的移动被阻挡，克隆体 B 将不会移动。
- 这不会阻止 Hero A 的移动。
- 如果 Hero A 试图向被障碍物或墙壁阻挡的方向迈出一步，他和克隆体 B 都不会移动。
此外，Hero A 需要尽快完成考试，以免考官意识到（他们不会注意到，对吧？）他从一开始就不在那里！求 Hero A 为了让克隆体 B 到达终点所需的最少步数。
输入格式
输入的第一行包含一个整数 $T$，即测试用例的数量。接下来是 $T$ 个测试用例的描述。
每个测试用例的第一行包含两个空格分隔的正整数 $r$ 和 $c$——网格 A 和网格 B 的行数和列数。
接下来是 $r$ 行，每行包含一个长度为 $c$ 的字符串。这编码了网格 A 的状态。
接下来是另外 $r$ 行，每行包含一个长度为 $c$ 的字符串。这编码了网格 B 的状态。
每个网格中可能出现的字符如下：
- “.”：空地
- “X”：障碍物
- “S”：起点（Hero A 在网格 A 中的起点，或克隆体 B 在网格 B 中的起点）
- “D”：克隆体的终点/目标（仅出现在网格 B 中）
输出格式
对于每个测试用例，输出一个整数，对应到达终点所需的最少移动步数。如果终点不可达，则输出 -1。
数据范围
$1 \le T \le 10$ $1 \le r, c \le 100$ $2 \le r \times c \le 1000$ “S”在网格 A 和网格 B 中各出现且仅出现一次。 “D”在网格 B 中出现且仅出现一次。
样例
样例输入 1
2 5 5 S.... ..... ..... ..... ..... ....S ..... ..... ..... ....D 7 5 XXXXX XXXXX XS..X X.X.X X...X XXXXX XXXXX XXXXX XS..X XXX.X X...X XXX.X XD..X XXXXX
样例输出 1
4 14
说明 1
在第一个测试用例中，尽管 Hero A 和克隆体 B 的起点不同，但 Hero A 只需要向下移动，克隆体 B 就能到达终点。
在第二个测试用例中，Hero A 可以通过在他的网格中“顺时针”走两圈，让克隆体 B 以最优步数到达终点。
图 1. 网格 A 和网格 B 的示意图