Petya 和 Vasya 喜欢参加 Codeforces 竞赛。瓦夏 (Vasya) 与佩蒂亚 (Petya) 打赌,他将参加比他更多的额定比赛。最初,Vasya 的评级为 $$$R_0$$$。总共将进行 $$$n$$$ 轮,每轮为以下两种类型之一:
- 分区。 1 — 对所有参与者评分
- 分区。 2 — 对评级严格低于 $$$X$$$ 的参与者进行评级,对所有其他参与者未评级,
在未评级的回合中,Vasya 无法更改他的评级。如果 Vasya 在评级轮之前的评级为 $$$R$$$,那么对于任何 非负 $$$R-D$$$ 和 $$$R+D$$$(含)之间的整数 $$$x$$$ Vasya 可以采取一种策略,使他的评分之后恰好变为 $$$x$$$(这里 $$$D$$$ 是正整数)。请注意,评级可能永远不会变为负面。
帮助 Vasya 确定他可以参加的最大额定轮数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含四个整数: $$$R_0, X, D, n$$$ ($$$0 \leq R_0 \leq 10^9$$$, $$$1 \leq X \leq 10^9$$$, $$$1 \leq D, n \leq 1000$$$) — Vasya 的初始评级,之间的评级阈值分区、最大评级增量和轮数。
每个测试用例的第二行包含一个大小为 $$$n$$$ 的字符串。该字符串仅包含字符“1“和”2”,代表div。 1 和分区。分别进行2轮。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^4$$$。
输出
对于每个测试用例,打印一个整数 - Vasya 可以参与的最大评级轮数。
示例
输入复制
42100 2100 5 32222098 2100 5 61112112115 2100 226 722111210 10 4 822111121
输出复制
0658
注意
在第一个示例中,由于 $$$R_0 \geq X$$$,每个 div. 2轮是 未评级 Vasya,所以他的评级永远不会改变。因此,他不能为自己进行任何一轮评级,答案是$$$0$$$。
在第二个示例中,每轮后的最佳评级序列之一是: $$$2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$$$。