Задано квадратное уравнение ax^2 + bx + c ≡ 0 (mod p), где a > 0 и p – нечетное простое число.
Ваша задача выяснить, имеет ли оно решение в целых числах.
В первой строке входного файла задано количество тестов t (1 ≤ t ≤ 100000). Каждый тест состоит из одной строки, содержащей четыре целых числа a, b, c, p, разделенных одним пробелом (3 ≤ p ≤ 2·10^9, 0 < a ≤ p–1, 0 ≤ b, c ≤ p–1). Гарантируется, что входные данные удовлетворяют описанным в условии задачи ограничениям.
Для каждого теста выведите строку, содержащую "YES" если уравнение имеет решение, и "NO" в противном случае.