A16293 | 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!

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.

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