Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:
-
Пусть 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 |