Mirko 和 Slavko 有一款新的棋盘游戏。游戏棋盘类似于一棵完全无限二叉树。更具体地说，棋盘由节点和连接它们的双向道路组成。根节点位于棋盘的最上方，我们称其处于第 0 层。每个节点都有且仅有两个子节点，即左子节点和右子节点，分别位于父节点的左下方和右下方。子节点的层数比父节点的层数大 1。除了连接父节点与子节点的道路外，还有连接同一层所有节点的道路——对于每一层，从最左边的节点开始，有一条道路将每个节点连接到同一层右侧的相邻节点。

图 1：下方的第二个样例

棋盘上的每条路径都是一个步骤序列，每一步都通过一条道路从一个节点移动到另一个不同的节点。每一步可以用单个字符描述如下：

• 字符 1 表示从一个节点移动到其左子节点，
• 字符 2 表示从一个节点移动到其右子节点，
• 字符 U 表示从一个节点移动到其父节点，
• 字符 L 表示从一个节点移动到同一层左侧的相邻节点，
• 字符 R 表示从一个节点移动到同一层右侧的相邻节点。

例如，如果我们从根节点开始，执行步骤序列 221LU，我们将到达上图中用字母 “A” 表示的节点。

任务

编写一个程序，在给定棋盘上两个节点的情况下，求出从一个节点到另一个节点所需的最少步数。这两个节点是通过指定从根节点到它们的路径来给出的。如果两条路径指向同一个节点，则答案为 0。

输入格式

输入的第一行包含一个长度最多为 $100\,000$ 的字符序列——从根节点到第一个节点的路径。

输入的第二行包含一个长度最多为 $100\,000$ 的字符序列——从根节点到第二个节点的路径。

这两条路径都是合法的（即两个序列中的每一步移动都是可行的）。

输出格式

输出的唯一一行应包含一个整数——从一个节点移动到另一个节点所需的最少步数。

子任务

设 $D$ 为满足以下条件的最小整数：输入的两条路径所访问的所有节点的层数均不超过 $D$。

• 在总分值为 20 分的测试点中，$D \le 10$。
• 在总分值为 40 分的测试点中，$D \le 50$。
• 在总分值为 70 分的测试点中，$D \le 1000$。

样例

输入样例 1

111RRRRRRR
222

输出样例 1

0

输入样例 2

221LU
12L2

输出样例 2

3

输入样例 3

11111
222222

输出样例 3

10