Với mỗi truy vấn gồm bốn số ~a, b, c, d~, hãy tìm số nguyên không âm lớn nhất ~x~ sao cho ~a \times x^{4} + b \times x^{2} + c \le d~. Nếu bất phương trình vô nghiệm, in ~-1~.

Dữ liệu vào

Dòng đầu chứa ~q~.

~q~ dòng tiếp theo, mỗi dòng chứa ~a~, ~b~, ~c~ và ~d~.

Dữ liệu ra

Gồm ~q~ dòng, mỗi dòng là đáp án của một truy vấn.

Giới hạn

~1 \le q \le 100000~, ~1 \le a, b, c \le 1000~, ~1 \le d \le 10^{18}~.

Ví dụ

Input

1
1000 1000 1000 1

Output

-1