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.
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.
For each test case output a string containing a "YES" if the equation has a solution, and "NO" otherwise.