题目描述

In a two-dimensional Cartesian coordinate system, you begin at the origin $(0,0)$.

You are given a string $s$ of length $n$, representing a walking sequence. The $i$-th character $s_i$ belongs to the set $\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$.

An infinitely long string $s'$ is constructed by repeating $s$ indefinitely. Formally, $s'_i = s_{((i - 1) \bmod n) + 1}$.

Now, you process each character of $s'$ in order, moving according to the following rules:

• If $s'_i = \texttt{U}$, move to $(x, y+1)$.
• If $s'_i = \texttt{D}$, move to $(x, y-1)$.
• If $s'_i = \texttt{L}$, move to $(x-1, y)$.
• If $s'_i = \texttt{R}$, move to $(x+1, y)$.

This process continues indefinitely. You are also given $m$ key points, where the $i$-th key point has coordinates $(p_i, q_i)$. Your task is to determine the number of $\textbf{distinct}$ key points that are visited during the infinite walking process.

输入格式

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^5$), the number of test cases. For each test case:

• The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^5$), where $n$ is the length of the string $s$ and $m$ is the number of key points.
• The second line contains the string $s$ of length $n$.
• The next $m$ lines each contain two integers $p_i$ and $q_i$ ($-10^9 \le p_i, q_i \le 10^9$), representing the coordinates of a key point.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $5 \cdot 10^5$.

输出格式

For each test case, output a single line containing a single integer, representing the number of distinct key points visited.

3
6 3
DUDUDU
0 0
1 0
0 -1
6 5
DUDULU
0 0
-1 0
0 -1
-1 -1
-1 1
5 5
ULUUL
-624531741 651883826
-1 2
-312566309 468849463
-212530129 633866239
672824982 -674189680

2
4
2

提示

In the first test case, only two key points $(0,0)$ and $(0,-1)$ are visited.

In the second test case, four key points $(0,0),(0,-1),(-1,0)$ and $(-1,1)$ are visited.