B. 机器人程序
每个测试点的时间限制：$2$ 秒
每个测试点的内存限制：$512$ 兆字节

有一条直线，上面有一个机器人。机器人的初始位置在点 $x$（$x \neq 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$ 点的次数。

示例
输入

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 \to 1 \to 0 \to -1 \to -2 \to -1$。机器人执行完所有指令后不在 $0$ 点，所以它在 $5$ 秒后停止。其间进入 $0$ 点 $1$ 次。
• 第二个示例：机器人移动路径为：$-1 \to 0 \to 1 \to 0 \to 1 \to 0 \to 1 \to 0 \to 1$。机器人工作 $8$ 秒，进入 $0$ 点 $4$ 次。
• 第三个示例：机器人移动路径为：$-2 \to -3 \to -2 \to -1 \to 0 \to -1$。机器人工作 $5$ 秒，进入 $0$ 点 $1$ 次。
• 第四个示例：机器人移动路径为：$3 \to 2 \to 3 \to 4 \to 3 \to 2$。机器人执行完所有指令后不在 $0$ 点，所以它在 $5$ 秒后停止，从未到达 $0$ 点。