This page is still under construction.

Parts of this page are still being built. What you see may change.

Johnny and the Quadratic Equation

Time limit1sMemory limit512 MB

Summary
Decide whether a quadratic congruence modulo 2^32 has a solution in x.
Level

Hard8 of 10

Topics
Number theory, Math, Bit manipulation
Solved
No attempts yet

Problem

Johnny just learned about quadratic equations. As an eager young programmer, he immediately wrote the following program to help with his homework:

#include<cstdio>
int main() {
    unsigned int a,b,c,x=0;
    scanf("%u %u %u",&a,&b,&c);
    do {
        if (a*x*x+b*x+c==0) {
            puts("YES");
            return 0;
        }
        x++;
    } while(x);
    puts("NO");
    return 0;
}

Every calculation is done on unsigned 32-bit integers (that is, modulo 2322^{32}). The program tries every unsigned 32-bit value of xx in turn and prints YES as soon as it finds one with a⋅x2+b⋅x+c≡0(mod232)a \cdot x^2 + b \cdot x + c \equiv 0 \pmod{2^{32}}; if no such xx exists it prints NO. Unfortunately this brute-force loop is far too slow, even on his brand-new gaming rig. Can you reproduce its output quickly?

Input

The first line contains an integer tt (t≤104t \le 10^4), the number of test cases. Each of the next tt lines contains three space-separated integers aa, bb, and cc (0≤a,b,c<2320 \le a, b, c < 2^{32}).

Output

For each test case, print YES if there exists an unsigned 32-bit integer xx with a⋅x2+b⋅x+c≡0(mod232)a \cdot x^2 + b \cdot x + c \equiv 0 \pmod{2^{32}}, and NO otherwise. Print each answer on its own line, in the order the test cases are given.

Examples1

  1. Example 1

    Input
    3
    948 43958 1429912782
    95348 54988 345335
    943428 4353958 3444096692
    
    Expected output
    YES
    NO
    YES