题目描述

派对最后，Alice 要给朋友们煎松饼。

Alice 有 $n$ 个未煎的松饼，但只有两口锅。初始时，前 $\min(n,2)$ 个松饼在锅上，所有松饼的熟度都是 $0$。

Alice 可以任意次执行以下两种操作：

• 同时煎两口锅上的松饼 $1$ 分钟。第一口锅上的松饼熟度增加 $a$，第二口锅上的松饼熟度增加 $b$。
• 端走第一口锅上的松饼，把第二口锅上的松饼移动到第一口锅，并把一个新的未煎松饼放到第二口锅（如果还有完全未煎的松饼）。这个操作不耗时，也可以连续执行多次。

如果只剩一个松饼，它会在第一口锅上，每分钟熟度增加 $a$，直到 Alice 决定端走它。

一个松饼当且仅当熟度恰好等于 $k$ 时是完美的。请你求出最多能端出多少个完美松饼。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据一行包含四个整数 $n,a,b,k$。

输出格式

对于每组测试数据，输出最多能得到的完美松饼数量。

数据范围

• $1 \le t \le 1000$
• $1 \le n,a,b,k \le 10^9$

7
17 1 1 1
123456789 987 654 321
3 11 37 111111
987654321 1 2 123456789
100 1 2 1
100 1 2 2
1 1 1 1

17
0
2
987654320
50
67
1

提示

在第一个测试案例中，爱丽丝可以完美地烹制出两份煎饼中的所有煎饼。因此，完美烹制煎饼的最大数量为 $17$ 。

在第二个测试案例中，由于两个平底锅都太热，爱丽丝总是会烤过头。因此，完全熟透的煎饼的最大数量为 $0$ 。

在第三种测试情况中，爱丽丝可以将前两个煎饼在平底锅上放置 $3003$ 分钟，然后将两个煎饼都端上桌，其中一个煎得不熟，另一个煎得很熟。至于最后一个煎饼，她将其放在平底锅上 $10\,101$ 分钟后再食用，使其完全熟透。由于没有办法将前两个煎饼完全烤熟（当第一个煎饼完全烤熟时，第二个煎饼已经烤过头了），所以完全烤熟的煎饼的最大数量是 $2$ 。

来源

Codeforces Round 2232 F - The Cake Is a Lie