说明

有一个 Y 形路口，包含四根车道以及它们交出的两个道路单元 $x,y$，以及 $x,y$ 之间的道路连接处。车辆从 $q_1,q_2$ 两车道向前进入路口，通过两个道路单元中的一部分，转向两边的道路。

不妨称 $q_1$ 为左车道，$q_2$ 为右车道。

• $t$ 时刻从左车道进入路口的车辆：
  • 若左转，则占据 $t$ 时刻的 $x$ 道路单元。
  • 若右转，则占据 $t$ 时刻的 $x$ 道路单元，$t+0.5$ 时刻的道路连接处，和 $t+1$ 时刻的 $y$ 道路单元。
• $t$ 时刻从右车道进入路口的车辆：
  • 若左转，则占据 $t$ 时刻的 $y$ 道路单元，$t+0.5$ 时刻的道路连接处，和 $t+1$ 时刻的 $x$ 道路单元。
  • 若右转，则占据 $t$ 时刻的 $y$ 道路单元。

由于道路是单根单行道，所以同一车道中前面的车辆一定比后面的车辆更早进入路口。

你不希望同一时刻有两辆车占据同一道路单元或者占据道路连接处，因为这可能导致交通堵塞。

现在给你两根车道从前往后每辆车的左右转情况，每辆车可以从 $1$ 时刻起的整数时刻进入路口。你的任务是安排一种满足条件的每辆车进入路口的时间，并使得最晚离开路口的车辆离开路口的时间最小。

输入格式

本题包含多组测试。

第一行一个正整数 $T$。对于每组测试数据：

第一行两个正整数 $n,m$，分别表示左右车道的车辆数。

第二行一个长度为 $n$ 的字符串，仅包含 L 或 R。第 $i$ 个字符表示左车道从靠近路口的一端向后第 $i$ 辆车是左转（L）还是右转（R）。

第三行一个长度为 $m$ 的字符串，仅包含 L 或 R。第 $i$ 个字符表示右车道从靠近路口的一端向后第 $i$ 辆车是左转还是右转。

输出格式

共 $T$ 行，表示每组测试数据的答案。

4
2 3
LR
RLL
3 3
RLR
LLR
4 5
RLLR
LLRLR
10 7
LLLRLRLRRR
LLLRLRL

6
7
9
16

提示

样例 #1 解释

对于第一组数据：

• 在第 $1$ 时刻，左车道的第一辆车左转，右车道的第一辆车右转，两辆车互不干涉。
• 在第 $2$ 时刻，左车道的第二辆车右转，这将占用 $2$ 时刻的 $x$ 道路单元，$2.5$ 时刻的道路连接处，和 $3$ 时刻的 $y$ 道路单元。
• 在第 $4$ 时刻，右车道的第二辆车左转，这将占用 $4$ 时刻的 $y$ 道路单元，$4.5$ 时刻的道路连接处，和 $5$ 时刻的 $x$ 道路单元。
• 在第 $5$ 时刻，右车道的第三辆车左转，这将占用 $5$ 时刻的 $y$ 道路单元，$5.5$ 时刻的道路连接处，和 $6$ 时刻的 $x$ 道路单元。

在这种安排下，最晚离开路口的车辆（右车道第三辆车）于 $6$ 时刻离开路口。可以证明，这是最小的最晚离开路口时刻，故输出 $6$。

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 2\times 10^5$，$1\le \sum (n+m)\le 4\times 10^5$，保证输入的表示车流的字符串中只含有 L 和 R。

特殊性质 A：右车道不存在相邻两辆车右转。

特殊性质 B：对于每组测试数据，右车道至多只有 $10$ 辆右转的车辆满足其下一辆车也是右转的。

特殊性质 C：数据输入文件中 L 字符的出现次数不超过 $5000$。

后记

:::epigraph[——《2025 AMBITION》] 拿出成绩证明自己他假装看不明白 :::