This is the hard version of the problem. The only difference is that in this version $k \le 10^{12}$. You can make hacks only if both versions of the problem are solved.

Given a $w \times h$ rectangle on the $Oxy$ plane, with points $(0, 0)$ at the bottom-left and $(w, h)$ at the top-right of the rectangle.

You also have a robot initially at point $(0, 0)$ and a script $s$ of $n$ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.

The robot can only move inside the rectangle; otherwise, it will change the script $s$ as follows:

• If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
• If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).

Then, it will execute the changed script starting from the character which it couldn't execute.

An example of the robot's movement process, $s = \texttt{"ULULURD"}$

The script $s$ will be executed for $k$ times continuously. All changes to the string $s$ will be retained even when it is repeated. During this process, how many times will the robot move to the point $(0, 0)$ in total? Note that the initial position does NOT count.

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains four integers $n$, $k$, $w$, and $h$ ($1 \le n, w, h \le 10^6$; $1 \le k \le 10^{12}$).

The second line contains a single string $s$ of size $n$ ($s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$) — the script to be executed.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, print a single integer — the number of times the robot reaches $(0, 0)$ when executing script $s$ for $k$ times continuously.