Problems
Quadratic equation 1
Quadratic equation 1
Set by the quadratic equation ax^2 + bx + c ≡ 0 (mod p), where a > 0 and p – odd prime number.
Your task is to determine whether it has a solution in integers.
Input data
The first line of the input file contains the number of tests t (1 ≤ t ≤ 100000). Each test consists of one line containing four integers a, b, c, p, separated by a space (3 ≤ p ≤ 2·10^9, 0 < a ≤ p–1, 0 ≤ b, c ≤ p–1). It is guaranteed that the input data satisfy the condition described in the problem constraints.
Output data
For each test case output a string containing a "YES" if the equation has a solution, and "NO" otherwise.
Examples
Input example #1
3 1 2 1 7 1 3 1 7 1 3 1 11
Output example #1
YES NO YES