Our monk, while taking a stroll in the park, stumped upon a polynomial ( A X² + 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 X_o, that shall make my value atleast K i.e., A X_o² + B X_o + 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⁵
1 ≤ A,B,C ≤ 10⁵
1 ≤ K ≤ 10¹⁰