坐标线上有一个机器人。最初,机器人位于点 $$$x$$$ ($$$x \ne 0$$$)。机器人有一个长度为 $$$n$$$ 的命令序列,由字符组成,其中 L 表示向左移动一个单位(从点 $$$p$$$ 到点 $$$(p-1)$$$)并且 R 表示向右移动一个单位(从点 $$$p$$$ 到点 $$$(p+1)$$$)。
机器人开始执行这一系列命令(每秒一个命令,按照它们出现的顺序)。然而,每当机器人到达 $$$0$$$ 点时,已执行命令的计数器就会重置(即它从头开始执行整个命令序列)。如果机器人已完成所有命令且不在 $$$0$$$ 处,则它将停止。
你的任务是计算机器人在接下来的$$$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}$$$)。
测试用例的第二行包含一个由 $$$n$$$ 字符组成的字符串 $$$s$$$ L 和/或 R.
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 机器人在接下来的 $$$k$$$ 秒内进入点 $$$0$$$ 的次数。
示例
输入复制
63 2 6LLR2 -1 8RL4 -2 5LRRR5 3 7LRRLL1 1 1L3 -1 4846549234412827RLR
输出复制
1 4 1 0 1 2423274617206414
注意
在第一个示例中,机器人移动如下:$$$2 \rightarrow 1 \rightarrow \underline{0} \rightarrow -1 \rightarrow -2 \rightarrow -1$$$。机器人已完成序列中的所有指令,并且不在 $$$0$$$ 处。因此它会在 $$$5$$$ 秒后停止,并且输入一次 $$$0$$$ 点。
在第二个示例中,机器人移动如下:$$$-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$$$ 输入一次。
在第四个示例中,机器人移动如下:$$$3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$。机器人已完成序列中的所有指令,并且不在 $$$0$$$ 处。因此它会在 $$$5$$$ 秒后停止,而不会到达 $$$0$$$ 点。