U736570 E - 熊大快跑
题目背景
请你完成熊大的任务，博美人一笑。
题目描述
熊大最开始位于数轴上的位置 $x$，保证 $x\ne 0$。
现在有一个长度为 $n$ 的指令串 $s$。
其中：
* `L` 表示熊大向左移动 $1$ 个单位；
* `R` 表示熊大向右移动 $1$ 个单位。
熊大每秒执行一个指令，并按照字符串 $s$ 从左到右依次执行。
但是熊大有一个特殊的习惯：
每当熊大到达位置 $0$ 时，他都会立刻从指令串的第一个指令重新开始执行。
如果熊大已经执行完整个指令串，并且此时没有位于位置 $0$，那么熊大就会停止奔跑。
现在请你计算，在接下来的 $k$ 秒内，熊大一共会到达位置 $0$ 多少次。
输入格式
第一行输入一个整数 $T$，表示测试数据组数。
对于每组测试数据：
第一行输入三个整数 $n,x,k$，分别表示指令串的长度、熊大的初始位置以及统计的时间。
第二行输入一个长度为 $n$ 的字符串 $s$。
字符串仅由字符 `L` 和 `R` 组成。
输出格式
对于每组测试数据，输出一行一个整数，表示在接下来的 $k$ 秒内，熊大到达位置 $0$ 的次数。
说明/提示
#### **样例解释**
对于第一组数据，熊大的移动过程为：
$$
2\rightarrow1\rightarrow0
$$
此时熊大第一次到达位置 $0$，随后会从指令串的第一个指令重新开始执行。
最终，在 $6$ 秒内熊大一共到达位置 $0$：
$$
1
$$
次。
#### **数据范围**
对于所有测试数据，保证：
$$
1\le T\le10^4
$$
对于每组测试数据：
$$
1\le n\le2\times10^5
$$
$$
-n\le x\le n,\qquad x\ne0
$$
$$
n\le k\le10^{18}
$$
字符串 $s$ 的长度恰好为 $n$，且仅包含字符 `L` 和 `R`。
此外，所有测试数据中的 $n$ 之和不超过：
$$
2\times10^5
$$
详细的子任务限制如下：
| 子任务 | 分值 | 特殊性质 |
| :-: | :--: | :------------------ |
| 1 | 50 分 | 所有测试数据的 $k$ 之和不超过 $10^6$ |
| 2 | 50 分 | 无特殊限制 |