{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid 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.\u003c/p\u003e\n\n\u003cp\u003eThere are 4 types of valid instructions in total, which are \u0027U\u0027 (up), \u0027D\u0027 (down), \u0027L\u0027 (left) and \u0027R\u0027 (right). Assuming that the robot is currently at $(x,y)$, the instructions control the robot in the way below:\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eU: Moves the robot to $(x,y+1)$.\u003c/li\u003e\n \u003cli\u003eD: Moves the robot to $(x,y-1)$.\u003c/li\u003e\n \u003cli\u003eL: Moves the robot to $(x-1,y)$.\u003c/li\u003e\n \u003cli\u003eR: Moves the robot to $(x+1,y)$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eThe full instruction sequence can be derived from the following equations $\\begin{cases} s_i \u003d a_i \u0026amp; \\text{if } 1 \\le i \\le n \\\\ s_i \u003d s_{i-n} \u0026amp; \\text{otherwise} \\end{cases}$\u003c/p\u003e\n\n\u003cp\u003eThe 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.\u003c/p\u003e\n\n\u003cp\u003eRecall 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|$.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers $n$ and $k$ ($1 \\le n \\le 10^5, 1 \\le k \\le 10^9$), indicating the length of the basic instruction sequence and the repeating parameter.\u003c/p\u003e\n\n\u003cp\u003eThe second line contains a string $A \u003d a_1a_2\\dots a_n$ ($|A| \u003d n$, $a_i \\in \\{\\text{\u0027L\u0027},\\text{\u0027R\u0027},\\text{\u0027U\u0027},\\text{\u0027D\u0027}\\}$), where $a_i$ indicates the $i$-th instruction in the basic instruction sequence.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $|A|$ of all test cases will not exceed $2 \\times 10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer indicating the answer.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3\nRUL\n1 1000000000\nD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor 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\u0027s obvious that the farthest point on the route is (1, 3) and the answer is 4.\u003c/p\u003e\n"}}]}