题目描述

给你一个可以用 $n×m$ 网格表示的房间。在位置 $(i_1,j_1)$（行 $i_1$ 和列 $j_1$ 的交叉点）有一个球，它开始沿四个方向之一对角移动：

球向下向右移动，用 DR 表示；这意味着在一步之后，球的位置从 $(i,j)$ 变为 $(i+1,j+1)$。

球向下向左移动，用 DL 表示；这意味着在一步之后，球的位置从 $(i,j)$ 变为 $(i+1,j-1)$。

球向上向右移动，用 UR 表示；这意味着在一步之后，球的位置从 $(i,j)$ 变为 $(i-1,j+1)$。

球向上向左移动，用 UL 表示；这意味着在一步之后，球的位置从 $(i,j)$ 变为 $(i-1,j-1)$。

在每一步之后，球都会保持其方向，除非它撞到墙上，在这种情况下，球的行进方向会沿着墙的轴翻转；如果球碰到一个角落，两个方向都会翻转。任何这种情况都被称为反弹。球从不停止运动。

在上面的例子中，球从 (1,7) 开始，向 DL 方向移动，直到到达底壁，然后反弹并继续向 UL 方向移动。到达左墙后，球反弹并继续朝 UR 方向前进。当球到达上壁时，它会反弹并沿 DR 方向继续。到达右下角后，它会弹一次并沿 UL 方向继续，依此类推。

您的任务是找出球在到达房间中的单元格 $(i_2,j_2)$ 之前将经历多少次反弹，或者通过输出 -1 表示它无法到达单元格 $(i_2,j_2)$。

请注意，如果一开始就在目标位置，视为直接到达；如果目标单元格在墙边，球到达该单元格时不需要计算反弹次数。

输入格式

第一行包含单个整数 $t(1≤t≤1000)$ ——测试用例的数量。

每个测试用例的第一行包含六个整数和一个字符串 $n,m,i_1,j_1,i_2,j_2,d$。

$(2≤n,m≤25000;1≤i_1,i_2≤n;1≤j_1,j_2≤m;d∈{DR,DL,UR,UL})$ -网格的尺寸、球的起始坐标、最终单元格的坐标和球的起始方向。

保证所有测试用例的 $n×m$ 之和不超过 $5×10^4$。

输出格式

对于每个测试用例，输出一个整数——球第一次到达单元格 $(i_2,j_2)$ 之前的反弹次数，或者如果球从未到达目标单元格，则输出 -1。

测试样例

6
5 7 1 7 2 4 DL
5 7 1 7 3 2 DL
3 3 1 3 2 2 UR
2 4 2 1 2 2 DR
4 3 1 1 1 3 UL
6 4 1 2 3 4 DR

3
-1
1
-1
4
0