CF2161A.Round Trip

They say that if you do 1000 rounds, there's a secret cartoon in the end (c)

Petya and Vasya love participating in Codeforces contests. Vasya made a bet with Petya that he will take part in more rated rounds than him. Initially, Vasya's rating is $R_0$. There will be $n$ rounds conducted in total, each of one of two types:

• div. 1 — rated for all participants
• div. 2 — rated for participants with rating strictly less than $X$, and unrated for all others,

In an unrated round, Vasya cannot change his rating. If Vasya's rating before a rated round was $R$, then for any non-negative integer $x$ between $R-D$ and $R+D$ (inclusive) Vasya can adopt a strategy such that his rating becomes exactly $x$ afterwards (here $D$ is a positive integer). Note that rating may never become negative.

Help Vasya determine the maximum number of rated rounds he can participate in.

据说如果参加 1000 轮比赛，最后会有一个隐藏的卡通图（c）

佩佳和瓦夏热衷于参加 Codeforces 比赛。瓦夏与佩佳打赌，称自己参与的**有评级（rated）**轮次将比佩佳更多。初始时，瓦夏的评分为 $R_0$。总共将举行 $n$ 轮比赛，每轮为以下两种类型之一：

• Div. 1 —— 对所有参赛者均为有评级轮次；
• Div. 2 —— 仅对评分严格小于 $X$ 的参赛者为有评级轮次，对其他所有人均为无评级（unrated）轮次；

在无评级轮次中，瓦夏的评分不会发生变化。若瓦夏在某一轮有评级轮次前的评分为 $R$，则对于任意满足 $R-D \le x \le R+D$ 的非负整数 $x$（含端点），瓦夏均可通过某种策略使该轮结束后其评分为恰好 $x$（此处 $D$ 是一个正整数）。注意：评分永远不会变为负数。

请帮助瓦夏确定他最多能参与多少轮有评级的比赛。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains four integers: $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's initial rating, the rating threshold between divisions, the maximum rating delta, and the number of rounds.

The second line of each test case contains a string of size $n$. The string will only contain the characters "1" and "2", representing div. 1 and div. 2 rounds respectively.

The sum of $n$ across all test cases does not exceed $3 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）—— 分别表示瓦夏的初始评分、两个分组之间的评分阈值、最大评分变化量以及比赛轮数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串。该字符串仅由字符 "1" 和 "2" 组成，分别代表第 1 分组和第 2 分组的比赛。

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

For each test case, print a single integer — the maximum number of rated rounds Vasya can participate in.

对于每个测试用例，输出一个整数——Vasya 最多能参加的有评级的比赛场数。

In the first example, since $R_0 \geq X$, each div. 2 round is unrated for Vasya, so his rating never changes. Therefore, he cannot make any round rated for himself, and the answer is $0$.

In the second example, one of the optimal sequences of ratings after each round is: $2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$.

在第一个例子中，由于 $R_0 \geq X$，Vasya 参加的每一场“Div. 2”比赛均为非计分赛，因此他的评分永远不会发生变化。因此，他无法使任何一场比赛对自己变为计分赛，答案为 $0$。

在第二个例子中，每轮比赛后评分的一种最优变化序列为：$2098 \rightarrow 2103 \rightarrow 2101 \rightarrow 2099 \rightarrow 2097 \rightarrow 2097 \rightarrow 2092$。