Description

DreamGrid 制作了一个可编程机器人，用于探索无限二维平面。机器人有一个基础指令序列 $a_1, a_2, \dots a_n$ 和一个“重复参数” $k$，二者合起来形成完整的指令序列 $s_1, s_2, \dots, s_n, s_{n+1}, \dots, s_{nk}$，用以控制机器人。

一共有 4 种有效指令，分别为 U（上）、D（下）、L（左）和 R（右）。假设机器人当前位于 $(x, y)$，指令对机器人的控制如下：

• U：机器人移动到 $(x, y+1)$。
• D：机器人移动到 $(x, y-1)$。
• L：机器人移动到 $(x-1, y)$。
• R：机器人移动到 $(x+1, y)$。

完整指令序列由如下公式生成：

$$\begin{cases} s_i = a_i & \text{如果 } 1 \le i \le n \\ s_i = s_{i-n} & \text{否则} \end{cases}$$

机器人初始位置为 $(0, 0)$，依次按顺序执行完整指令序列中的每一条指令，总共执行 $nk$ 条指令。为了评估探索过程，DreamGrid 想要计算机器人在执行全部 $nk$ 条指令过程中，距离起点 $(0, 0)$ 的最大曼哈顿距离。

回顾一下，$(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $\left| x_1 - x_2 \right| + \left| y_1 - y_2 \right|$。

Input Format

输入包含多组测试数据。第一行输入一个整数 $T$，表示测试用例的个数。对于每个测试用例：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 10^5, 1 \le k \le 10^9$），分别表示基础指令序列的长度和重复参数。

第二行输入一个字符串 $A = a_1a_2\dots a_n$ （$|A|=n$，$a_i$ 取值为 L、R、U、D 中的一个），代表基础指令序列中的第 $i$ 个指令。

保证所有测试用例中所有字符串 $A$ 的长度之和不超过 $2 \times 10^6$。

Output Format

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

2
3 3
RUL
1 1000000000
D

4
1000000000

Hint

对于第一个样例，最终的指令序列是 RULRULRUL，机器人的轨迹依次为 $(0, 0) \to (1, 0) \to (1, 1) \to (0, 1) \to (1, 1) \to (1, 2) \to (0, 2) \to (1, 2) \to (1, 3) \to (0, 3)$。显然轨迹上最远的点是 $(1, 3)$，曼哈顿距离为 $4$，答案为 $4$。

由 ChatGPT 5 翻译