题目描述

Monocarp 是 Berland 州立大学的一名学生。由于 Berland 教育体系的最新变动，Monocarp 现在只需要学习一门课程——编程。

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

实践任务会按“每周”逐步解锁：第一个任务在第 $1$ 天解锁（可以在第 $1$ 天到第 $n$ 天中的任意一天完成），第二个任务在第 $8$ 天解锁（可以在第 $8$ 天到第 $n$ 天中的任意一天完成），第三个任务在第 $15$ 天解锁，依此类推。

从第 $1$ 天到第 $n$ 天，每天都有一节课，Monocarp 都可以选择参加。每天，Monocarp 可以选择学习或休息一天。如果他选择学习，则当天会参加一节课，并且可以完成不超过 $2$ 个已经解锁且尚未完成的任务。如果选择休息，则当天既不参加课程，也不完成任务。

Monocarp 希望尽可能多地休息，也就是说，他想最大化休息天数。请你帮他计算，在不被开除的前提下，他最多可以休息多少天？

输入格式

第一行包含一个整数 $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 每天都学习并完成所有任务，则一定可以获得足够的分数，不会被开除。

输出格式

对于每个测试用例，输出一个整数，表示 Monocarp 最多可以休息多少天而不会被开除。

说明/提示

在第一个测试用例中，学期只有 $1$ 天，所以 Monocarp 只能在第 $1$ 天学习。仅仅参加一次课程就能获得 $5$ 分（$5 \ge P$），所以是否完成任务无关紧要。

在第二个测试用例中，Monocarp 可以在第 $8$ 天和第 $9$ 天学习：第 $8$ 天参加一次课程获得 $10^9$ 分，并完成两个任务各获得 $5 \cdot 10^8$ 分。第 $9$ 天只需参加课程再获得 $10^9$ 分。

在第三个测试用例中，Monocarp 可以在第 $42$ 天学习：参加一次课程获得 $1$ 分，完成 $6$ 个任务中的 $2$ 个再获得 $2 \cdot 10$ 分。

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

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

由 ChatGPT 4.1 翻译

样例

5
1 5 5 2
14 3000000000 1000000000 500000000
100 20 1 10
8 120 10 20
42 280 13 37

0
12
99
0
37