Euclidean Algorithm#413
Dmytryk has recently started learning computer science. One of the first algorithms he studied was the Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers. Recall that for two numbers and , the GCD is the greatest natural number that divides both and without remainder.
The Euclidean algorithm works as follows:
Let and be the numbers whose GCD is to be found.
If b = 0, then is the GCD.
If b > a, swap and .
Assign the value a - b.
Return to step 2.
Dmytryk quickly mastered the Euclidean algorithm and computed many GCDs using it. Soon, he came up with a new problem. Given numbers , , , and , determine whether, during the execution of the Euclidean algorithm for the pair , there is a moment just before step 2 when a = c and b = d.
Write a program to solve this problem.
The first line contains the number of input data sets (1 \leq k \leq 100). The descriptions of these sets follow. Each description consists of two lines. The first line contains two integers: , (1 \leq a, b \leq 10^{18}). The second line contains two integers: , (1 \leq c, d \leq 10^{18}). All numbers in the lines are separated by spaces.
For each set of input data, print YES on a separate line if, during the application of the Euclidean algorithm to the pair , the pair is encountered at any moment, or NO otherwise.
Example 1