题目描述

在坐标轴上有一个机器人。初始时，机器人位于点 $x$（$x \ne 0$）。机器人有一个长度为 $n$ 的命令序列，由字符组成，其中 L 表示向左移动一个单位（从点 $p$ 移动到点 $(p-1)$），R 表示向右移动一个单位（从点 $p$ 移动到点 $(p+1)$）。

机器人开始执行这个命令序列（每秒执行一个命令，按顺序执行）。然而，每当机器人到达点 $0$ 时，已执行命令的计数器会被重置（即它会从头开始重新执行整个命令序列）。如果机器人完成了所有命令且未处于 $0$ 点，它将停止运行。

你的任务是计算在接下来的 $k$ 秒内，机器人会进入点 $0$ 多少次。

输入格式

本题有多组数据

第一行包含一个整数 $t$，代表 $t$ 组数据。

• 每组数据的第一行包含三个整数 $n$、$x$ 和 $k$。

• 每组数据的第二行包含一个由 $n$ 个字符 L 或 R 组成的字`符串 $s$。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每一组数据，输出一个整数——在接下来的 $k$ 秒内机器人进入点 $0$ 的次数。

6
3 2 6
LLR
2 -1 8
RL
4 -2 5
LRRR
5 3 7
LRRLL
1 1 1
L
3 -1 4846549234412827
RLR

1
4
1
0
1
2423274617206414

提示

• 第一个示例中，机器人移动路径为：$2 \rightarrow 1 \rightarrow \underline{0} \rightarrow -1 \rightarrow -2 \rightarrow -1$。机器人完成了序列中的所有指令且未处于 $0$ 点，因此在 $5$ 秒后停止，点 $0$ 被进入 $1$ 次。

• 第二个示例中，机器人移动路径为：$-1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1 \rightarrow \underline{0} \rightarrow 1$。机器人运行了 $8$ 秒，点 $0$ 被进入 $4$ 次。

• 第三个示例中，机器人移动路径为：$-2 \rightarrow -3 \rightarrow -2 \rightarrow -1 \rightarrow \underline{0} \rightarrow -1$。机器人运行了 $5$ 秒，点 $0$ 被进入 $1$ 次。

• 第四个示例中，机器人移动路径为：$3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2$。机器人完成了序列中的所有指令且未处于 $0$ 点，因此在 $5$ 秒后停止，未到达点 $0$。

数据范围

对于 $100\%$ 的数据满足，$1\leq t\leq 10^4,1\leq n\leq 2\cdot 10^5,-n\leq x\leq n,n\leq k\leq 10^{18}$，保证初始时 $x\not= 0$，保证所有数据 $\sum n \leq 2\cdot 10^5$ 即所有组数据 $n$ 的和不超过 $2\cdot 10^5$。

• 子任务 $1$ （$30$ 分）：$n\leq k\leq 10^3$。
• 子任务 $2$ （$30$ 分）：保证 $n=k$。
• 子任务 $3$ （$40$ 分）：无特殊限制。