Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:
-
Пусть a
, b
— числа, НОД которых надо найти.
-
Если b = 0
, то число a
— искомый НОД.
-
Если b > a
, то необходимо поменять местами числа a
и b
.
-
Присвоить числу a значение a – b
.
-
Вернуться к шагу 2.
Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a
, b
, c и d
, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b)
наступает такой момент, когда перед исполнением шага 2 число a
будет равно c
, а число b
будет равно d
.
Напишите для Маши программу, которая проверит, удовлетворяют ли числа a
, b
, c
, 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
».
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2
20 10
10 10
10 7
2 4 |
YES
NO |