T440703 「YAC Round 10」人偶巨大化计划


爱丽丝为了提升自己的战斗力，于是开始研发巨大人偶，比如歌莉娅。 爱丽丝可以操纵歌莉娅朝上、下、左、右四个方向进行移动（分别用 $\text{'U', 'D', 'L', 'R'}$ 表示），假设歌莉娅位于 $(x, y)$ ： - $\text{'U'}$： 移动到 $(x - 1, y)$ ； - $\text{'D'}$： 移动到 $(x + 1, y)$ ； - $\text{'L'}$： 移动到 $(x, y - 1)$ ； - $\text{'R'}$： 移动到 $(x, y + 1)$ 。 爱丽丝有一个长度为 $n$ 的基本指令序列 $a$ 和一个重复参数 $k$，现在需要重复 $k$ 轮按照基本指令序列 $a$ 进行移动。 假设重复 $k$ 轮一共的移动序列为 $s$： $$ \begin{cases} s_i = a_i, & 1 \le i \le n \\ s_i = s_{i-n}, & n + 1 \le i \le nk \end{cases} $$ 现在，在一个无限大的网格图上，歌莉娅初始的位置为 $(0, 0)$，然后爱丽丝会重复 $k$ 轮按照基本指令序列逐个指令操纵歌莉娅完成移动。 请你求出歌莉娅在整个移动过程中（共 $nk$ 次移动），**距离起点 $(0, 0)$ 最大的曼哈顿距离**。 提示：$(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$ 。

**有多组测试数据** 第一行输入一个整数 $T$ $\;$ ($1 \le T \le 20$) — 表示测试数据组数。 对于每组测试数据： 第一行输入两个整数 $n$ 和 $k$ $\;$ ($1 \le n \le 10^5$, $1 \le k \le 10^9$) — 分别表示基本指令序列的长度 和 重复参数。 第二行输入一个长度为 $n$ 的字符串 $a$ $\;$ ($a_i \in \{ \text{'U', 'D', 'L', 'R'} \}$) — 表示基本指令序列，其中 $a_i$ 表示基本指令序列中的第 $i$ 个指令。

对于每组测试数据： 输出一个整数，表示整个移动过程中距离起点 $(0, 0)$ 的最大曼哈顿距离。