To end the party, Alice decides to cook some pancakes for her friends.

Alice has $$$n$$$ uncooked pancakes but only $$$2$$$ pans. Initially, the first $$$min(n,2)$$$ pancakes are on the pans, and all pancakes have cookedness $$$0$$$.

To cook her pancakes, Alice may perform the following two operations any number of times:

Cook the two pancakes on the pans for $$$1$$$ minute. The pancake on the first pan's cookedness increases by $$$a$$$, and the pancake on the second pan's cookedness increases by $$$b$$$.
Serve the first pancake, move the second pancake to the first pan, and add a new uncooked pancake to the second pan (if there are any completely uncooked pancakes left). Note that this takes no time, and can be done multiple times in a row.

Note that if there is only one pancake left, it will be on the first pan, gaining $$$a$$$ cookedness per minute until Alice decides to serve it.

A pancake is perfectly cooked if and only if its cookedness is exactly $$$k$$$.

Help Alice find the maximum number of perfectly cooked pancakes that she can serve.

Input

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 only line in the test case contains $$$4$$$ integers $$$n$$$, $$$a$$$, $$$b$$$, and $$$k$$$ ($$$1 \le n,a,b,k \le 10^9$$$) — the number of pancake batter Alice has, the amount of cookedness the pancake on the first pan gains at the end of each minute, the amount of cookedness the pancake on the second pan gains at the end of each minute, and the amount of cookedness the pancake needs to have in order for it to be perfectly cooked.

Output

For each test case, output the maximum number of perfectly cooked pancakes Alice can make.

Note

In the first testcase, Alice can perfectly cook all pancakes in a batch of two. Therefore, the maximum number of perfectly cooked pancakes is $$$17$$$.

In the second test case, Alice will always overcook all pancakes since both pans are too hot. Therefore, the maximum number of perfectly cooked pancakes is $$$0$$$.

In the third test case, Alice can leave the first two pancakes on the pans for $$$3003$$$ minutes, then serve both of them, one undercooked and one perfectly cooked. For the last pancake, she leaves it on the pan for $$$10\,101$$$ minutes before serving it to make it perfectly cooked. Since there are no ways to perfectly cook the first two pancakes (by the time the first pancake is perfectly cooked, the second pancake will be overcooked), the maximum number of perfectly cooked pancakes is $$$2$$$.

The Cake Is a Lie

Examples