All Tracks>Algorithms> Searching> Binary Search> Problem
Monk's Encounter with Polynomial
★★★★★

3.8

221 votes
Algorithms, Approved, Binary Search, Easy, Math, Open, Sorting
Problem

Our monk, while taking a stroll in the park, stumped upon a polynomial ( A X2 + 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 Xo2 + 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 ≤ 105
1 ≤ A,B,C ≤ 105
1 ≤ K ≤ 1010

Sample Input
3
3 4 5 6
3 4 5 5
3 4 5 150
Sample Output
1
0
7
Time Limit: 2
Memory Limit: 256
Source Limit:
Contributers:
Editor Image

?