CF1902B.Getting Points

Monocarp is a student at Berland State University. Due to recent changes in the Berland education system, Monocarp has to study only one subject — programming.

The academic term consists of $n$ days, and in order not to get expelled, Monocarp has to earn at least $P$ points during those $n$ days. There are two ways to earn points — completing practical tasks and attending lessons. For each practical task Monocarp fulfills, he earns $t$ points, and for each lesson he attends, he earns $l$ points.

Practical tasks are unlocked "each week" as the term goes on: the first task is unlocked on day $1$ (and can be completed on any day from $1$ to $n$), the second task is unlocked on day $8$ (and can be completed on any day from $8$ to $n$), the third task is unlocked on day $15$, and so on.

Every day from $1$ to $n$, there is a lesson which can be attended by Monocarp. And every day, Monocarp chooses whether to study or to rest the whole day. When Monocarp decides to study, he attends a lesson and can complete no more than $2$ tasks, which are already unlocked and not completed yet. If Monocarp rests the whole day, he skips a lesson and ignores tasks.

Monocarp wants to have as many days off as possible, i. e. he wants to maximize the number of days he rests. Help him calculate the maximum number of days he can rest!

Monocarp 是贝尔兰国立大学的一名学生。由于贝尔兰教育体系的最新改革，Monocarp 在本学期内只需学习一门课程——编程。

整个学期共包含 $n$ 天，为了不被开除，Monocarp 必须在这 $n$ 天内至少获得 $P$ 分。获取分数的方式有两种：完成实践任务和参加课程。每完成一项实践任务，Monocarp 可获得 $t$ 分；每参加一节课，他可获得 $l$ 分。

实践任务按“每周”节奏逐步解锁：第 $1$ 项任务于第 $1$ 天解锁（可在第 $1$ 至 $n$ 天中的任意一天完成），第 $2$ 项任务于第 $8$ 天解锁（可在第 $8$ 至 $n$ 天中的任意一天完成），第 $3$ 项任务于第 $15$ 天解锁，依此类推。

从第 $1$ 天到第 $n$ 天，每天均安排有一节课，Monocarp 均可参加。而每一天，Monocarp 都需选择整日学习或整日休息。当 Monocarp 选择学习时，他必须参加当天的课程，并且最多可完成 $2$ 项已解锁且尚未完成的实践任务；若 Monocarp 选择整日休息，则跳过当天课程，且忽略所有实践任务。

Monocarp 希望拥有尽可能多的休息日，即最大化其休息天数。请帮助他计算他最多可以休息多少天！

The first line contains a single integer $tc$ ($1 \le tc \le 10^4$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains four integers $n$, $P$, $l$ and $t$ ($1 \le n, l, t \le 10^9$; $1 \le P \le 10^{18}$) — the number of days, the minimum total points Monocarp has to earn, the points for attending one lesson and points for completing one task.

It's guaranteed for each test case that it's possible not to be expelled if Monocarp will attend all lessons and will complete all tasks.

第一行包含一个整数 $tc$（$1 \le tc \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅一行，包含四个整数 $n$、$P$、$l$ 和 $t$（$1 \le n, l, t \le 10^9$；$1 \le P \le 10^{18}$），分别表示天数、Monocarp 需要获得的最低总分、出席一节课所得分数以及完成一项任务所得分数。

保证对于每个测试用例，若 Monocarp 出席所有课程并完成所有任务，则一定不会被开除。

For each test, print one integer — the maximum number of days Monocarp can rest without being expelled from University.

对于每次测试，输出一个整数——Monocarp 在不被大学开除的情况下最多可以休息的天数。

In the first test case, the term lasts for $1$ day, so Monocarp should attend at day $1$. Since attending one lesson already gives $5$ points ($5 \ge P$), so it doesn't matter, will Monocarp complete the task or not.

In the second test case, Monocarp can, for example, study at days $8$ and $9$: at day $8$ he will attend a lesson for $10^9$ points and complete two tasks for another $5 \cdot 10^8 + 5 \cdot 10^8$ points. And at day $9$ he only attends a lesson for another $10^9$ points.

In the third test case, Monocarp can, for example, study at day $42$: attending a lesson gives him $1$ point and solving $2$ out of $6$ available tasks gives him another $2 \cdot 10$ points.

In the fourth test case, Monocarp has to attend all lessons and complete all tasks to get $8 \cdot 10 + 2 \cdot 20 = 120$ points.

In the fifth test case, Monocarp can, for example, study at days: $8$ — one lesson and first and second tasks; $15$ — one lesson and the third task; $22$ — one lesson and the fourth task; $29$ — one lesson and the fifth task; $36$ — one lesson and the sixth task.

在第一个测试用例中，学期持续 $1$ 天，因此 Monocarp 应在第 $1$ 天参加课程。由于仅参加一节课即可获得 $5$ 分（$5 \ge P$），因此 Monocarp 是否完成任务已无关紧要。

在第二个测试用例中，Monocarp 可以例如在第 $8$ 天和第 $9$ 天学习：在第 $8$ 天，他参加一节价值 $10^9$ 分的课程，并完成两项任务，额外获得 $5 \cdot 10^8 + 5 \cdot 10^8$ 分；而在第 $9$ 天，他仅参加一节价值 $10^9$ 分的课程。

在第三个测试用例中，Monocarp 可以例如在第 $42$ 天学习：参加一节课获得 $1$ 分，从当前可选的 $6$ 项任务中完成其中 $2$ 项，额外获得 $2 \cdot 10$ 分。

在第四个测试用例中，Monocarp 必须参加全部 $8$ 节课并完成全部 $2$ 项任务，才能获得 $8 \cdot 10 + 2 \cdot 20 = 120$ 分。

在第五个测试用例中，Monocarp 可以例如在以下日期学习：第 $8$ 天——参加一节课并完成第一、二项任务；第 $15$ 天——参加一节课并完成第三项任务；第 $22$ 天——参加一节课并完成第四项任务；第 $29$ 天——参加一节课并完成第五项任务；第 $36$ 天——参加一节课并完成第六项任务。