Evklid Alqoritmi
Dima informatika öyrənməyə yeni başlayıb. Onun öyrəndiyi ilk alqoritmlərdən biri, iki ədədin ən böyük ortaq bölənini (ƏBOB) tapmaq üçün Evklid alqoritmi idi. Xatırladaq ki, iki ədəd a və b üçün ƏBOB, həm a, həm də b ədədlərini qalıqsız bölən ən böyük təbii ədəd x-dir.
Evklid alqoritmi belə işləyir:
a və b — ƏBOB tapılmalı olan ədədlərdir.
Əgər b = 0 olarsa, a ƏBOB-dur.
Əgər b > a olarsa, a və b ədədlərinin yerlərini dəyişmək lazımdır.
a ədədinə a – b qiymətini mənimsətmək.
2-ci addıma qayıtmaq.
Dima Evklid alqoritmini tez bir zamanda mənimsədi və onun köməyi ilə çoxlu ƏBOB-lər hesabladı. Tezliklə ona yeni bir məsələ həll etmək fikri gəldi. Gəlin a, b, c və d ədədləri verilsin. Verilmiş (a, b) ədədlər cütü üçün Evklid alqoritminin icrası prosesində elə bir anın olub-olmadığını öyrənmək lazımdır ki, 2-ci addımın icrasından əvvəl a ədədi c-yə, b ədədi isə d-yə bərabər olsun.
Bu məsələni həll edən proqram yazmaq lazımdır.
Giriş verilənləri
Birinci sətir, giriş məlumat dəstlərinin sayı olan k (1 ≤ k ≤ 100) ədədini ehtiva edir. Sonra bu dəstlərin təsviri gəlir. Hər təsvir iki sətirdən ibarətdir. Birinci sətir iki tam ədəd ehtiva edir: a, b (1 ≤ a, b ≤ 10^18). İkinci sətir isə iki tam ədəd ehtiva edir: c, d (1 ≤ c, d ≤ 10^18). Sətirdəki bütün ədədlər boşluqla ayrılmışdır.
Çıxış verilənləri
Hər bir giriş məlumat dəsti üçün ayrıca sətirdə «YES» sözünü çıxarın, əgər Evklid alqoritminin (a, b) ədədlər cütü üçün tətbiqi prosesində hər hansı bir anda (c, d) cütü alınarsa, və ya «NO» sözünü çıxarın – əks halda.