Tyrion Lannister wants to pay Bronn reward for his services. Being a Lannister, he has an unlimited number of coins of denominations A, and B. He has also got an unlimited number of bags, in which he can give the money. Each bag can contain at most N rupees. Tyrion wants to pay Bronn at least M rupees.
As you know, Tyrion cannot lift many bags, so he wants to minimise the number of bags. Also, all the bags should contain the same amount.
Can you help Tyrion in finding the minimum number of bags required?
INPUT
First line contains T the number of test-cases. The only line of each test case contains four integers - M,N,A,B.
OUTPUT
For each test case, print the minimum number of bags required in one line.
CONSTRAINTS
1≤T≤10
1≤M≤1018
1≤A,B≤N≤106
For the first test case, one of the possible ways is to put 2 coins of A, and 1 coin of B in each bag. Thus, 3 bags are enough to get a sum of at least 27.
It is easy to see that there is no way to obtain the sum with a lesser number of bags.
