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{if } 1 \le i \le n \\ s_i = s_{i-n} & \text{otherwise} \end{cases} $$
机器人最初位于 $(0, 0)$，并依次执行完整指令序列中的指令。为了评估探索过程，DreamGrid 希望计算在执行 $nk$ 条指令的过程中，机器人与起点 $(0, 0)$ 之间的最大曼哈顿距离。
回想一下，$(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。
输入格式
输入包含多组测试数据。第一行包含一个整数 $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 \in \{‘L’, ‘R’, ‘U’, ‘D’\}$)，其中 $a_i$ 表示基本指令序列中的第 $i$ 条指令。
保证所有测试数据的 $|A|$ 之和不超过 $2 \times 10^6$。
输出格式
对于每组测试数据，输出一行，包含一个整数，表示答案。
样例
输入 1
2 3 3 RUL 1 1000000000 D
输出 1
4 1000000000
说明
对于第一个样例，最终的指令序列为 “RULRULRUL”，机器人的路径为 $(0, 0) - (1, 0) - (1, 1) - (0, 1) - (1, 1) - (1, 2) - (0, 2) - (1, 2) - (1, 3) - (0, 3)$。显然，路径上距离起点最远的点是 $(1, 3)$，答案为 $4$。