该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

TG T4 fdj.cpp

Description

在无限二叉树里有一只负毒鸡，这是一只由小 H 开发的机器鸡，它可以按照给定的指令进行操作，初始位于 1 号节点即根节点。与其他机器不同的是，负毒鸡是一个复读机，即执行完当前指令后，它会将指令再执行一遍，然后再执行一遍，直到小 H 把他关掉。在二叉树中负毒鸡的指令有以下三种：

1. L走向左儿子节点。
2. R 走向右儿子节点。
3. T 返回父亲节点（若没有父亲节点，则该操作不合法，负毒鸡将会损坏）。

在这个无限二叉树上，存在 $n$ 个宝藏，它们是联通的。如果负毒鸡到了这些存在宝藏的节点，会将宝藏取走。如果负毒鸡到了非宝藏点，也能够行走，但是不会获得任何宝藏。

小 H 是一名狂热的完美主义者，他要求必须找到一条最短的指令使得负毒鸡能够把所有的宝藏全部取得。由于指令的方法可能有多种，所以小 H 希望你输出指令的最短长度。

Format

Input

输入共一行。

第一行，输入一个长度为 $n$ 只包含 AELR 的字符串，表示宝藏联通二叉树的前序遍历。

• A 表示该节点有两个儿子。
• E 表示该节点没有子儿子。
• L 表示该节点只有左儿子。
• R 表示该节点只有右儿子。

Output

输出一个数 $ans$，表示最短可以使得负毒鸡找到所有宝藏的指令。

Samples

AAREEE

3

AALALARAEREEEEE

9

样例 3 参见附件 fdj03.in\fdj03.ans。

Explanation

Sample 1 Explanation

其中一种可行的指令为 RTL。

Sample 2 Explanation

其中一种可行的指令为 RRRTTLTTL。

Limitation

对于 $100\%$ 的数据，$1\leq n\leq 2000$。

时空限制：1000ms/256MB。