Задача C. Алгоритм Евклида

Автор:Рекомендации жюри Всероссийской олимпиады   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:50  

Условие

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

  1. Пусть a, b — числа, НОД которых надо найти.
  2. Если b = 0, то число a — искомый НОД.
  3. Если b > a, то необходимо поменять местами числа a и b.
  4. Присвоить числу a значение a − b.
  5. Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Наконец, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Первая строка входного файла содержит количество наборов входных данных k. Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа a b, а вторая — два целых числа: c d.

Формат выходного файла

Для каждого набора входных данных выведите в отдельной строке выходного файла слово "YES", если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d), или слово "NO" в противном случае.

Ограничения

1 ≤ k ≤ 100, 1 ≤ a, b, c, d ≤ 1018

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
20 10
10 10
10 7
2 4
YES
NO

0.135s 0.009s 13