Evklid algoritmi - ikki sonni eng katta umumiy bo'luvchisini(EKUB) topib beruvchi effektiv algoritm hisoblanadi. Algoritm yunon matematiki Evklid nomiga berilgan. U bu algoritmni eramizidan 3 asr oldin o'ylab topgan. Evklid algoritmi ikkita musbat son uchun yangi juftlikni hosil qiladi, kattasini kichginasi orqali kamaytirib. Bu jarayon ikkala son teng bo'lib qolmaguncha davom ettiriladi.

Misol tariqasinda $(12, 14)$ juftligini olaylik. Dastlab $12$ ni $14$ olib tashlaymiz. Hosil bo'lgan juftlik - $(12, 2)$. Keyin shu jarayon taqrorlanadi:

$EKUB(12, 2) = EKUB(10, 2) = EKUB(8, 2) = EKUB(6, 2) = EKUB(4, 2) = EKUB(2, 2) = 2.$ Shunday qilib javob - $2$. Bu algoritmini to'g'riligiga sabab agarda $d = EKUB(a, b)$ bo'lsa demak ikki sonni ayirmasi ham $d$ soniga bo'linadi. Ya'ni $(a - b) = 0 (mod$ $d).$

Afsuski, bu algoritm agarda birorta son kichik bo'lib, boshqasi katta bo'lsa juda ko'p amal bajarishiga to'g'ri keladi. Masalan $(2, 10000001)$ juftligi uchun $5000000$ amal bajariladi $EKUB$i birligini aniqlash uchun. Ya'ni eng yomon holatda algoritm $O(max(a, b))$ amal bajarishiga to'g'ri keladi. Buni yanada tez ishlaydigan qilish mumkin. Gap shundaki har safar katta son kichkinasidan $max(a, b) / min(a, b)$ challi ayrilib tashlanadi. Ayirish o'rninga qoldiq olish amalini bajarish mumkin. Shunda har safar katta son kichginadan kichiklashadi. Har safar ikkala sondan bittasi kamida $2$ baravar kichraygani uchun ishlash vahti $O(log(min(a, b)))$ tashkil qiladi.

Lekin gap shundaki amalda bu algoritm deyarli $O(1)$ amal bajaradi. Chunki har qanday juftlik uchun bittasi kamida ikki baravarga kichiklashadi dedik, ammo amalda bu kichrayish tezroq va kattaroq suratda bo'ladi. Masalan ushbu $(12, 14)$ juftlik uchun $EKUB$ni topish uchun $2$ amal kifoya etadi . Lekin shunda ham shunday juftliklar bor-ki ular uchun algoritm ko'p amal bajarishi mumkin. Sizga bu masalada $n$ soni berilgan bo'lib, siz shunday $(a,b)1 \le a < b \le n$ juftlikni topishingiz kerakki, bu juftliklar uchun Evklid algoritmi eng ko'p amalni bajarsin. Agarda bunday juftliklardan bir nechtasi bo'lsa $a$ si minimalini chiqaring, agarda $a$ si minimalidan bir nechta bo'lsa $b$ si minimal bo'lganni chiqaring. Boshqacha qilib aytgan leksiografik eng kichik javobni chiqaring.

Kiruvchi ma’lumotlar: Birinchi qatorda natural son $n(2 \le n \le 10^9)$.

Chiquvchi ma’lumotlar: Yagona qatorda masala yechimini chiqaring.