Euclidean Algorithm
Dima has recently embarked on his journey into computer science. One of the first algorithms he learned is the Euclidean algorithm, which is used to find the greatest common divisor (GCD) of two numbers. The GCD of two numbers a and b is the largest natural number x that divides both a and b without leaving a remainder.
The Euclidean algorithm follows these steps:
Start with the numbers a and b, whose GCD you want to find.
If b equals 0, then a is the GCD.
If b is greater than a, swap a and b.
Subtract b from a and assign the result to a.
Repeat from step 2.
Dima quickly became proficient with the Euclidean algorithm and used it to compute many GCDs. He then thought of a new challenge: Given numbers a, b, c, and d, determine if there is a point during the execution of the Euclidean algorithm on the pair (a, b) where, just before step 2, the numbers a and b are equal to c and d, respectively.
Your task is to write a program that solves this problem.
Input
The first line contains the number of test cases k (1 ≤ k ≤ 100). Each test case is described in two lines. The first line contains two integers: a and b (1 ≤ a, b ≤ 10^18). The second line contains two integers: c and d (1 ≤ c, d ≤ 10^18). All numbers are separated by spaces.
Output
For each test case, output "YES" on a separate line if, during the execution of the Euclidean algorithm on the pair (a, b), the pair (c, d) appears at some point. Otherwise, output "NO".