Cho 4 số nguyên a, b, c, k. Tìm giá trị nhỏ nhất của x sao cho ~ax^2+bx+c >= k~.

Input:

• Dòng 1. Ghi số nguyên dương T là số test.
• T dòng tiếp theo lần lượt là các test, mỗi test gồm một dòng chứa lần lượt a, b, c, k.

Output:

• In ra kết quả cần tìm trên một dòng với mỗi test.

• Example:

Input:

2
4 6 5 5
1 2 3 4

Output:

0
1

Constraints:

~1 \le T \le 100 ; 1 \le a, b, c \le 10^5 ; 1 \le k \le 10^{12}; 0 \le x \le 10^5~