Алгоритм Евкліда#413

Алгоритм Евкліда

1 секунда

122,174 мегабайта

Середня

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

Алгоритм Евкліда полягає у наступному:

Нехай $a$ і $b$ — числа, НСД яких потрібно знайти.
Якщо $b = 0$ b = 0, то $a$ — шуканий НСД.
Якщо $b > a$ b > a, поміняти місцями $a$ і $b$ .
Присвоїти числу $a$ значення $a - b$ a - b.
Повернутися до кроку 2.

Дмитрик швидко освоїв алгоритм Евкліда і за його допомогою знайшов багато найбільших спільних дільників. Незабаром йому спало на думку розв'язати нову задачу. Нехай задано числа $a$ , $b$ , $c$ і $d$ . Потрібно дізнатися, чи настане у процесі реалізації алгоритму Евкліда для заданої пари чисел $(a, b)$ такий момент, коли перед виконанням кроку 2 буде виконуватись $a = c$ a = c і $b = d$ b = d.

Напишіть програму для розв'язання цієї задачі.

Вхідні дані

Перший рядок містить кількість наборів вхідних даних $k$ ( $1 \leq k \leq 100$ 1 \leq k \leq 100). Далі йде опис цих наборів. Кожен опис складається з двох рядків. Перший з них містить два цілих числа: $a$ , $b$ ( $1 \leq a, b \leq 1 0^{18}$ 1 \leq a, b \leq 10^{18}). Другий рядок містить два цілих числа: $c$ , $d$ ( $1 \leq c, d \leq 1 0^{18}$ 1 \leq c, d \leq 10^{18}). Усі числа у рядках відокремлені пробілом.

Вихідні дані

Для кожного набору вхідних даних виведіть в окремому рядку слово YES, якщо у процесі застосування алгоритму Евкліда до пари чисел $(a, b)$ у якийсь момент отримається пара $(c, d)$ , або слово NO — у протилежному випадку.

Приклади

Приклад 1