Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.
Euclid's algorithm is as follows:
Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Вскоре ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.
Требуется написать программу, которая решает эту задачу.
Первая строка содержит количество наборов входных данных k (1 ≤ k ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 10^18). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 10^18). Все числа в строках разделены пробелом.
Для каждого набора входных данных выведите в отдельной строке слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d), или слово «NO» – в противном случае.