在二维笛卡尔坐标系中，你从原点 $(0, 0)$ 开始。

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

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

现在，你按顺序处理 $s'$ 的每个字符，并根据以下规则进行移动：

• 如果 $s'_i = U$，移动到 $(x, y + 1)$。
• 如果 $s'_i = D$，移动到 $(x, y - 1)$。
• 如果 $s'_i = L$，移动到 $(x - 1, y)$。
• 如果 $s'_i = R$，移动到 $(x + 1, y)$。

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

请注意，多个关键点可能会重合，在这种情况下，它们仍被视为不同的关键点。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 5 \cdot 10^5$)，表示测试用例的数量。对于每个测试用例：

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

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

输出格式

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

样例

输入样例 1

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

输出样例 1

2
4
2

说明

在第一个测试用例中，仅访问了两个关键点 $(0, 0)$ 和 $(0, -1)$。

在第二个测试用例中，访问了四个关键点 $(0, 0)$、$(0, -1)$、$(-1, 0)$ 和 $(-1, 1)$。