该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在《我的世界》这个充满无限可能的方块世界中，Steve 作为一名勇敢的探险家，总是渴望探索未知的领域。最近，他在一片神秘的森林深处发现了一个古老的遗迹，遗迹中藏有一张破旧的地图，上面标记着一系列复杂的坐标点。这些坐标点似乎指向了遗迹下方隐藏的宝藏，但要找到它们，Steve 必须解开一个与红石科技相关的谜题。

在遗迹的中心，有一个由红石电路驱动的机关，这个机关控制着一扇通往地下的大门。要启动这个机关，Steve 需要通过一系列精确的指令来操作红石机器人，使其在坐标轴上移动到特定的点。机器人的移动由一系列 'L'（向左移动）和 'R'（向右移动）指令控制，每次移动一个单位。每当机器人到达坐标原点 0 时，机器人会从头开始执行指令序列，直到它完成了所有指令且未处于原点 0（或时间已经过去了k秒，指令没执行完也要结束）。

没读懂题意的多看看样例以及样例下面的说明和提示（多看看第一个样例和第二个样例的提示，尤其是第二个）。

这个挑战不仅考验着Steve 对红石科技的理解，还考验着他的逻辑思维和策略规划能力。他必须计算出在接下来的 k 秒内，机器人会进入原点 0 多少次。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $k$（$1 \le n \le 2 \cdot 10^5$；$-n \le x \le n$；$n \le k \le 10^{18}$），分别表示指令序列的长度、机器人的起始位置和Steve 需要计算的秒数。

每个测试用例的第二行包含一个由 n 个字符 'L' 和/或 'R' 组成的字符串 s，表示机器人的移动指令序列。

输入额外约束：所有测试用例的 n 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数——在接下来的 k 秒内机器人进入原点 0 的次数。

输入输出样例 #1

输入 #1

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

输出 #1

1
4
1
0
1
2423274617206414

说明/提示

在第一个测试用例中，机器人从位置 2 开始，执行指令 LLR，它在 5 秒后停止，原点 0 被进入 1 次。模拟过程（模拟过程里的数字依次表示第1秒到第6秒所处的位置（注意：第0秒是在2的位置，接下来是从第1秒开始表示的））：1->0->-1->-2->-1(在第5秒结束（因为在第5秒时它完成了所有指令且未处于原点 0），没有第6秒的了）,可以看到只有1个0，所以是经过了1次。

在第二个测试用例中，机器人从位置 -1 开始，执行指令 RL，它在 8 秒内四次经过原点 0。模拟过程（模拟过程里的数字依次表示第1秒到第8秒所处的位置（注意：第0秒是在-1的位置，接下来是从第1秒开始表示的））：0->1->0->1->0->1->0->1,可以看到有4个0，所以是经过了4次。（多想想，第1秒是0，第二秒为什么是1，有没有可能是序列还没执行完，但是到达了0的位置，要从序列的开头开始执行？（位置不用从初始位置开始，是字符串序列要从头开始））。

第三个测试用例中，机器人从位置 -2 开始，执行指令 LRR，它在 5 秒内经过原点 1 次。

第四个测试用例中，机器人从位置 3 开始，执行指令 LRR，它在 5 秒后停止，未到达原点 0。