Antonina has hryvnias. A ticket to the first cinema costs hryvnias, and a ticket to the second cinema costs hryvnias.
Initially, she may buy tickets to either cinema. At any moment, including before her first purchase, she may multiply her remaining money by at most once. After the multiplication, she may buy tickets only to the second cinema.
Find the maximum number of tickets Antonina can buy.
The first line contains one integer (1\le t\le10^5) — the number of test cases.
Each of the next lines contains four integers , , , and (1\le n,a,b,x\le10^9, a\le b).
For each test case, print one integer — the maximum number of tickets.
Example 1
Example 2
Example 3
In the first test case of the first example, she can immediately multiply hryvnias by and buy tickets for hryvnias each. In the second test case, she will have hryvnias after the multiplication, enough for tickets. In the third test case, she can buy ticket after the multiplication.
In the first test case of the second example, she can buy tickets to the first cinema without multiplying her money. In the second test case, she can buy tickets. In the third test case, she cannot afford any ticket even after the multiplication.
Subtask ( points): t,n,a,b,x\le1000.
Subtask ( points): t,n,a,b,x\le10^5.
Subtask ( points): no additional constraints.