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