题目描述

他们说如果你打了 1000 场，就能看到最后的隐藏动画片（c）。

Petya 和 Vasya 都喜欢参加 Codeforces 比赛。Vasya 和 Petya 打赌，他能比 Petya 参加更多场计分轮。最初，Vasya 的 rating 为 $R_0$。一共会举办 $n$ 场比赛，每场比赛属于以下两种类型之一：

• div. 1 —— 对所有参赛者计分；
• div. 2 —— 仅对 rating 严格小于 $X$ 的选手计分，对其他人不计分。

在一场不计分的比赛中，Vasya 的 rating 不会发生变化。如果 Vasya 在某场计分轮前的 rating 是 $R$，那么对于任意非负整数 $x$，且 $x$ 满足 $R-D \leq x \leq R+D$（其中 $D$ 为正整数），Vasya 可以采用某种策略，使得他在该轮之后的 rating 恰好变为 $x$。注意，rating 永远不会变为负数。

请帮助 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 的初始 rating，分区的 rating 阈值，rating 的最大变化量，以及比赛的总轮数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串，只包含字符 ‘1’ 和 ‘2’，分别表示该场比赛为 div. 1 輪 和 div. 2 輪。

所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^4$。

输出格式

对于每个测试用例，输出一个整数，表示 Vasya 最多可以参加多少场计分轮。

说明/提示

在第一个样例中，由于 $R_0 \geq X$，所以每一场 div. 2 的比赛对 Vasya 来说都不计分，因此他的 rating 从未变化。因此，他无法让任何一轮对自己计分，答案为 $0$。

在第二个样例中，一种最优的 rating 变化序列为：$2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$。

由 ChatGPT 5 翻译

样例

4
2100 2100 5 3
222
2098 2100 5 6
111211
2115 2100 226 7
2211121
0 10 4 8
22111121

0
6
5
8