Description

橙汁桃最近喜欢上一款经典游戏 2048，就是在一个 $n\times n$ 的格子图中上下左右移动合成数字，目标是合成出 2048，每次移动所有数字方块都会向移动方向滑去，直到被其他方块阻挡或者到达边界，如果两个相同的数字碰撞则会合成新的，新值为原来两个方块的和，每当有方块合成或者移动，结束后就会在空的位置随机出现一个新的方块。

可是笨笨的橙汁桃怎么都合不出来，于是他去请教大佬游戏攻略。大佬告诉他，只需主要移动两个方向即可，心急的橙汁桃并没有听完，听了一半就马上跑回去自己试试去了，他决定选择两个移动方向，然后一直轮流操作这两个方向直到无论多少次操作后都无法再有新的变化出现，可是出现的数字方块以及位置是随机的，他始终还是没法合成 2048。

于是他决定使用游戏修改器，可以修改下一次出现的数字方块上数字大小和位置，但似乎还是不能合成 2048 ，于是他转而想获得最高分数，可惜笨笨的他不会计算，所以请你帮他算算在他的策略下，最多能得多少分。

所得分数是最后状态 $n\times n$ 的格子中所有数字值之和，橙汁桃操作只会有两个不同方向交替执行，如 LR，则操作序列为 LRLRLRLR...，每次出现数字和位置都可以用修改器修改（包括初始状态时的一个方块）。

Input

第一行一个 $T$（$1\leq T\leq 100$），表示 $T$ 组数据

每组数据格式如下：第一行 $n,m$（$1\leq n\leq 15,1\leq m\leq 2048$），$n$ 表示 2048 游戏格子大小，$m$ 表示出现的数字范围在 $[1,m]$ 之间的整数，接下来一行两个字母表示操作，字母均为 L，R，U，D 中的一个，分别表示向左，右，上，下移动。

Output

对于每组数据，输出一行一个数字，表示能获得的最高分数。

Samples

4
2 2
RD
1 2
LR
2 4
DU
1 2048
LU

18
2
24
2048

Note

样例第一组的一种可行的方案：

答案为 $4+8+2+4=18$。

注意：答案可能超出 int 范围。

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛