eolymp
bolt
Try our new interface for solving problems
Problems

Quadratic equation 1

Quadratic equation 1

Time limit 2 seconds
Memory limit 64 MiB

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 (1t100000). Each test consists of one line containing four integers a, b, c, p, separated by a space (3p2·10^9, 0 < ap–1, 0b, cp–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
Author Evgeniy Sluzhaev