题目描述

徐老师和石老师为了反抗老板的压榨，决定在公司内部的每个部门进行游行！

公司内部的的部门布局类似于一棵倒着的满二叉树

1. 我们把大门也当成一个部门，编号为 $1$，处于第 $1$ 层
2. 每个编号为 $i$ 的部门有两个子部门，左侧部门编号为 $i * 2$，右侧部门编号为 $i * 2 + 1$，且 $i$ 号部门分别有一条通道连接到这两个子部门，可以通过通道往返于 i 号部门和子部门之间
3. 如果 $i$ 号部门处在第 $x$ 层，那么它的两个子部门就处在 $x + 1$ 层
4. 如果两个部门的编号相差 $1$，且它们处于同一部门，那么它们之间存在一条通道，可以通过这条通道往返这两个部门
5. 你可以认为这家公司的部门有无限多个

现在为了不被别人发现，徐老师决定使用暗语和石老师沟通游行路线

这个暗语会是一个字符串，从左往右依次表示每一次行动的方向

其中：

• $1$： 表示移动到当前部门的左侧子部门
• $2$： 表示移动到当前部门的右侧子部门
• $U$： 表示移动到当前部门的上层部门，例如 $5$ 号部门的上层部门是 $2$
• $L$： 表示移动到当前部门同层的左边那个部门（保证当前部门不会是这层最左侧的部门）
• $R$： 表示移动到当前部门同层的右边那个部门（保证当前部门不会是这层最右侧的部门）

现在徐老师和石老师已经分别告知了对方自己的游行路线

现在徐老师想知道，他们两个在游行结束后，最少需要移动几个部门才能找到对方？（以便于快速跑路）

输入格式

输入第一行包含一个字符串，表示徐老师的游行路线

输入第二行包含一个字符串，表示石老师的游行路线

输出格式

输出一个整数，表示最终答案

数据范围

设 $H$ 表示两人游行路线中会到达的最高层部门的层数，$len$ 表示游行路线字符串的长度

对于 $30\%$ 的数据保证：$1 \leq H \leq 10,1 \leq len \leq 100$；

对于 $60\%$ 的数据保证：$1 \leq H \leq 30,1 \leq len \leq 100$；

对于 $100\%$ 的数据保证：$1 \leq H \leq 50,1 \leq len \leq 100000$；

特别的，保证对于每段测试数据中的第一组数据，徐老师和石老师的终点是同一个部门

样例输入1

221LU
12L2

样例输出1

3

样例解释1

他们的行进路线如下图

可以发现最终两人之间相距 $3$ 次移动的距离

样例输入2

111RRRRRRR
222

样例输出2

0

样例输入3

11111
222222

样例输出3

10