Our monk, while taking a stroll in the park, stumped upon a polynomial ( A X^2 + B X +C ) lying on the ground. The polynomial was dying! Being considerate, our monk tried to talk and revive the polynomial. The polynomial said:
I have served my purpose, and shall not live anymore. Please fulfill my dying wish. Find me the least non-negative integer Xo, that shall make my value atleast K i.e., A Xo^2 + B Xo + C ≥ K .
Help our Monk fulfill the polynomial's dying wish!
Input:
The first line contains an integer T. T test cases follow.
Each test case consists of four space-separated integers A, B, C and K.

Output:
For each test case, output the answer in a new line.
Constraints:
1 ≤ T ≤ 10^5
1 ≤ A,B,C ≤ 10^5
1 ≤ K ≤ 10^10

SAMPLE INPUT
3
3 4 5 6
3 4 5 5
3 4 5 150

SAMPLE OUTPUT
1
0
7

见题面

见题面