Special Moves

Input

The first line contains an integer $t$ (1 \le t \le 10^5) — the number of test cases in a single input file.

Each test case is described in two lines. The first line contains integers $n$, $x$, $y$ — the length of the string $s$ and the coordinates of the starting point (1 \le n \le 2 \cdot 10^5), (-10^9 \le x, y \le 10^9).

The second line contains the string $s$ of length $n$ (s_i \in \{\mathtt{R}, \mathtt{L}, \mathtt{D}, \mathtt{U}\}).

It is guaranteed that the sum of $n$ across all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, output the number of special points.

Examples

Note

In the first test case, the process looks like this:

1. Initially, we are at $(1,1)$.

2. We move left, so we are at $(0,1)$.

3. We move up, so we are at $(0,2)$.

4. We move down, so we are at $(0,1)$.

5. We move up again, so we are at $(0,2)$.

6. We move down again, so we are at $(0,1)$.

Here, the most visited point is $(0,1)$, and it was visited $3$ times. Only one point among all was visited $3$ times.

In the second test case, the process looks like this:

1. Initially, we are at $(1,1)$.

2. We move left, so we are at $(0,1)$.

3. We move right, so we are at $(1,1)$.

4. We move left, so we are at $(0,1)$.

5. We move down, so we are at $(-1,1)$.

Here, the most visited points are $(0,1)$ and $(1,1)$, and they were visited $2$ times, so the answer is $2$.

Scoring

1. ($2$ points): n \le 2;

2. ($8$ points): s_i \in \{\mathtt{L}, \mathtt{R}\};

3. ($10$ points): (-100 \le x, y \le 100) - This is guaranteed at any point of the process;;

4. ($10$ points): (1 \le \sum n \le 500) ;

5. ($20$ points): no additional constraints;