Veshy is suffering in AP Physics! He has a series of 
~N~ tests coming up and he has come up with four parameters describing each test:
~n_i~ which indicates the number of problems on the 
~i~-th test
~a_i~ which indicates the number of points Veshy gets for one correct answer
~b_i~ which indicates the number of points Veshy loses for an incorrect or unanswered question
~t_i~ which indicates the score Veshy would like to earn on the ~i~-th test
For the ~i~-th test, output the minimum number of questions Veshy has to answer correctly in order to get at least ~t_i~ marks. If Veshy's standards are too high and he cannot get ~t_i~ marks on the ~i~-th test, then output -1.
Constraints
In all tests,
~1 \le N \le 100~
~1 \le n_i, a_i, b_i, t_i \le 10^9~
Input Specification
The first line contains one integer, ~N~, the number of tests to follow.
The next ~N~ lines contain four space-separated integers, ~n_i~ ~a_i~ ~b_i~ ~t_i~.
Output Specification
Output ~N~ lines. The ~i~-th line should contain one integer, the answer to the ~i~-th test.
Sample Input
5
1 4 2 5
9 2 6 4
2 9 3 5
3 5 2 10
8 2 5 7
Sample Output
-1
8
1
3
7
Comments
Somebody help check my code plzz
The value of
can go up to 
, which exceeds the maximum value for int (
) in java.
Edit: Also you may want to see if there is a way to get the value of j in a faster way.
The answer may overflow int