ممد و قلی تو فلسفه ی وجود یکسری جفت اعداد مسخره به مشکل خوردن. قلی میگه نباید وجود داشته باشن و ممد میگه مگه اصن وجود دارن؟؟ قلی میبینه که مشکل ممد یکم حاد تره و از شما میخواد کمکش کنین!

اولش به ما عدد $1\le n \le 50000$ رو میده و بعدش $n$ تا سوال از ما میپرسه که باید جواب بدیم, هرکدوم به این شکل:

$a, b, d$ ($۱\le d \le a, b \le 50000$)

به ازای هر پرسشی باید تعداد جفت اعدادی مثل $(x, y)$ رو خروجی بدیم که :
1) $1 \le x \le a$
۲) $1 \le y \le b$
۳) $gcd(x, y) = d$

و $gcd(x, y)$ یعنی بزرگترین مقسوم علیه مشترک اعداد $x$ و $y$.

در صبور نبودن ممد شکی نیست, پس همه ی جواب ها باید زیر 8 ثانیه حاضر بشن.

--منبع : المپیاد لهستان

بروزرسانی: داشتم دینی میخوندم فکر کنم حلش کردم! = )
راه حلش خیلی قشنگه! الان نمیذارم چون میخوام برم ادامه ی دینی رو بخونم(D:) و همچنین میخوام شمام روش فکر کنین!
یسری راهنمایی:
1)آفلاین بزنین! یعنی اول همه ی پرسش ها رو بگیرین بعد به هر ترتیبی که خودتون دوست دارین جوابشون رو پیدا کنین و بعد به ترتیب ورودی جوابشون رو خروجی بدین!
۲)همونجور که @حمیدرضاهدایتی گفت میتونیم فرض کنیم همیشه d=1. حالا فرض کنید جواب پرسش $(a, b)$ بشه $ans(a, b)$. حالا $ans(a+1, b)$ (و همچنین $ans(a, b + ۱)$) رو از روی $ans(a, b)$ پیدا کنین!
۳) بعد از این دو تا کار بالا، یه ایده ی قشنگ میخوره که با استفاده از همین الگوریتم که اینجا گفته شد، مسئله حل میشه!

پی نوشت آخر: $O(\sqrt n(nlogn + mlogm))$ حلش کنین!! ($m$ بزرگترین عدد تو ورودیه.)