Another Totient problem by Ankur Sir J. He is madly in love with totient. Let’s see what he has prepared this time.

Recently he was studying integral properties of Quadratic functions. He found some interesting notions of real and complex numbers through Quadratic functions. But as you know he is a big totient fan, he mixed totient with quadratic functions this time and that resulted into a nice problem. He wants to find out if there exists a real root ‘x’ in the equation below:

Totient(a*x^2 + b*x + c) = k

Given ‘a’, ‘b’, ‘c’ and ‘k’, output “Yes” if a real root exists or “No” if no real root exists.

Input

First line contains T, the no. of test cases.

Each of the next T lines contains a, b, c and k.

Output

Output T lines, each for a single test case, containing either a “Yes” or a “No” corresponding to the test case.

Constraints

0 < T <= 100

0 < a <= 10^6

0 < b <= 10^6

0 < c <= 10^6

0 < k <= 10^6

b^2 >= 4*a*c

Example

Input:
2
1 4 3 4
1 21 11 10

Output:
Yes
Yes