Description

在一个二维笛卡尔坐标系中，你从原点 $(0,0)$ 出发。

给定一个长度为 $n$ 的字符串 $s$，表示一段行走指令序列。第 $i$ 个字符 $s_i$ 属于集合 $\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$。

将字符串 $s$ 无限次重复，构造出一条无限长的字符串 $s'$。形式化地，$s'_i = s_{((i - 1) \bmod n) + 1}$。

接着你依次处理 $s'$ 的每个字符，按照如下规则移动：

• 若 $s'_i = \texttt{U}$，则移动至 $(x, y+1)$。
• 若 $s'_i = \texttt{D}$，则移动至 $(x, y-1)$。
• 若 $s'_i = \texttt{L}$，则移动至 $(x-1, y)$。
• 若 $s'_i = \texttt{R}$，则移动至 $(x+1, y)$。

这一过程将无限持续下去。你还被给定了 $m$ 个关键点，其中第 $i$ 个关键点的坐标为 $(p_i, q_i)$。你的任务是求出在无限行走过程中被访问到的 不同的 关键点数量。

Input Format

输入包含多个测试用例。第一行是一个整数 $t$（$1 \leq t \leq 5 \cdot 10^5$），表示测试用例个数。对每个测试用例：

• 第一行包含两个整数 $n$ 与 $m$（$1 \le n, m \le 5 \cdot 10^5$），分别表示字符串 $s$ 的长度和关键点的数量。
• 第二行包含长度为 $n$ 的字符串 $s$。
• 接下来的 $m$ 行中，每行包含两个整数 $p_i$ 和 $q_i$（$-10^9 \le p_i, q_i \le 10^9$），表示一个关键点的坐标。

保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $5 \cdot 10^5$。

Output Format

对于每个测试用例，输出一行，包含一个整数，表示被访问到的不同关键点数量。

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

Hint

在第一个测试用例中，仅有两个关键点 $(0,0)$ 与 $(0,-1)$ 会被访问到。

在第二个测试用例中，有四个关键点 $(0,0)$、$(0,-1)$、$(-1,0)$ 与 $(-1,1)$ 会被访问到。

翻译由 ChatGPT-5 完成