Calico Bear 坚信没有人能超越他在贪吃蛇游戏中的高分。Busy Beaver 则不以为然，他想编写一个算法来证明 Calico Bear 是错的。

贪吃蛇游戏在一个无限大的二维网格上进行。蛇是由一系列不同的单元格组成的路径，从蛇头延伸到蛇尾，其中每一对相邻的单元格共享一条边。蛇的长度是它所包含的单元格数量。

游戏在时间 $t=0$ 时开始，此时只有一条长度为 1 的蛇，位于 $(0, 0)$，并且在其他某个位置有一个苹果。

Busy Beaver 将进行一系列 $N$ 次输入，输入集合为 $\{\text{L, R, D, U}\}$（左、右、下、上），以控制蛇的移动。每次输入都会按如下方式更新蛇的状态：首先，蛇头向指定方向移动一个单元格。蛇的其余每个单元格随后移动到前一个单元格之前占据的位置，原蛇尾位置变为空闲。如果蛇头移动到的单元格包含苹果，则苹果被吃掉，蛇在原蛇尾位置增加一个单元格。随后，一个新的苹果会在一个未被蛇占据的单元格中生成。

只有当更新后蛇的任意两个单元格不重合时，该输入才有效。题目保证没有任何输入与前一次输入方向相反。

设游戏得分为 $\sum_{t=0}^{N} L_t$，其中 $L_t$ 是时间 $t$（经过 $t$ 次输入后）蛇的长度。给定 $N$ 次输入序列，求在所有可能的苹果放置方案下，使得所有输入均有效的最大可能得分。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 5 \cdot 10^3$)。 接下来一行包含一个长度为 $N$ 的字符串 $s$ ($s_i \in \{\text{L, R, D, U}\}$)，其中 $s_i$ 表示 Busy Beaver 进行的第 $i$ 次输入。没有任何输入与前一次输入方向相反。 所有测试用例的 $N$ 之和不超过 $5 \cdot 10^3$。

输出格式

对于每个测试用例，输出一行一个整数作为答案。

子任务

• (60 分)：所有测试用例的 $N$ 之和不超过 500。
• (40 分)：无附加限制。

样例

输入 1

3
3
RRR
5
RDLUR
6
DDLURU

输出 1

10
18
22

说明

该样例包含三个测试用例。

在第一个测试用例中，蛇移动了 3 次。蛇可以在不发生自身碰撞的情况下吃掉 3 个苹果。得分为 $L_0 + L_1 + L_2 + L_3 = 1 + 2 + 3 + 4 = 10$。

在第二个测试用例中，蛇移动了 5 次。蛇的长度无法超过 4，因为它只占据 4 个单元格。得分为 $L_0 + L_1 + L_2 + L_3 + L_4 + L_5 = 1 + 2 + 3 + 4 + 4 + 4 = 18$。

在第三个测试用例中，蛇移动了 6 次。蛇的长度无法超过 4，因为它形成了一个 4 个单元格的环。在循环之后，蛇无法再次生长，因为苹果本应在时间 3 生成，而当时最终单元格被蛇尾占据。得分为 $L_0 + L_1 + L_2 + L_3 + L_4 + L_5 + L_6 = 1 + 2 + 3 + 4 + 4 + 4 + 4 = 22$。