Wandering Robot

题号：NC236064
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

DreamGrid creates a programmable robot to explore an infinite two-dimension plane. The robot has a basic instruction sequence $a_1, a_2, \dots a_n$ and a "repeating parameter" $k$ , which together form the full instruction sequence $s_1, s_2, \dots, s_n, s_{n+1}, \dots, s_{nk}$ and control the robot.

There are 4 types of valid instructions in total, which are `U' (up), `D' (down), `L' (left) and `R' (right). Assuming that the robot is currently at $(x,y)$ , the instructions control the robot in the way below:

U: Moves the robot to $(x,y+1)$ .
D: Moves the robot to $(x,y-1)$ .
L: Moves the robot to $(x-1,y)$ .
R: Moves the robot to $(x+1,y)$ .

The full instruction sequence can be derived from the following equations

$\begin{cases} s_i = a_i & \text{if } 1 \le i \le n \\ s_i = s_{i-n} & \text{otherwise} \end{cases}$

The robot is initially at $(0,0)$ and executes the instructions in the full instruction sequence one by one. To estimate the exploration procedure, DreamGrid would like to calculate the largest Manhattan distance between the robot and the start point $(0,0)$ during the execution of the $nk$ instructions.

Recall that the Manhattan distance between $(x_1,y_1)$ and $(x_2,y_2)$ is defined as $\left| x_1 - x_2 \right| + \left| y_1 - y_2 \right|$ .

输入描述:

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:
The first line contains two integers  and  (), indicating the length of the basic instruction sequence and the repeating parameter.
The second line contains a string  (, ), where  indicates the -th instruction in the basic instriction sequence.
It's guaranteed that the sum of  of all test cases will not exceed .

输出描述:

For each test case output one line containing one integer indicating the answer.

示例1

输入

复制

2
3 3
RUL
1 1000000000
D

输出

复制

4
1000000000

备注:

For the first sample test case, the final instruction sequence is "RULRULRUL" and the route of the robot is (0, 0) - (1, 0) - (1, 1) - (0, 1) - (1, 1) - (1, 2) - (0, 2) - (1, 2) - (1, 3) - (0, 3). It's obvious that the farthest point on the route is (1, 3) and the answer is 4.