Limits 1s, 512 MB

তারেক আবরার হলো একজন অলস প্রোগ্রামার। তার এক বন্ধুর নাম আমিনভাই, যে বিভিন্ন আশ্চর্যজনক দক্ষতার জন্য পরিচিত। আমিনভাইয়ের অনেক ফ্যান-ফলোয়ার আছে এবং বড় ধরনের একটা ফ্যান-ক্লাবও আছে। একদিন আমিনভাইকে তারেক একটা সমস্যার সমাধান করে দিতে বললো। কিন্তু, আমিনভাই তার নববিবাহিত স্ত্রীকে নিয়ে ব্যস্ত ছিল। সমস্যাটা সমাধানের উপায় খুঁজে না পেয়ে তারেক খুব হতাশ হয়ে পড়লো। আসলে এটা অনেক সহজ প্রশ্ন ছিল। কিন্তু, তারেক আবরার খুব অলস ছেলে। তাই সে তোমাকে সমস্যাটার সমাধান করে দিতে বলেছে। যদি তুমি এ সমস্যা সমাধান করতে পারো, তবে তুমি তারেকের একজন উপকারী বন্ধু হিসেবে গণ্য হবে।

তোমাকে দুটি ধনাত্মক পূর্ণসংখ্যা $N$ এবং $X$ দেয়া হবে। তোমাকে এমন সকল ধনাত্মক পূর্ণসংখ্যা M এর কথা চিন্তা করতে হবে, যেন $ M < NX $ এবং $M$, $N$ পরস্পর সহমৌলিক হয়। যদি $N$$X$ দিয়ে দেওয়া থাকে, তাহলে এমন সকল $M$ এর যোগফল আউটপুট দাও।

দুটি ধনাত্মক পূর্ণসংখ্যাকে পরস্পর সহমৌলিক বলা হয়, যদি তাদের গ.সা.গু. 1 হয়।

বুঝতেই পারছো, এটা অনেক সহজ সমস্যা। আশা করি, আমাদের অলস বন্ধু তারেক-কে তুমি সাহায্য করতে পারবে। 🙂

Input

ইনপুটে একাধিক টেস্টকেস থাকবে। প্রথম লাইনে একটি ধনাত্মক পূর্ণসংখ্যা $T$ ($ 1 \le T \le 5 \times 10^5 $) থাকবে, যেটি মোট টেস্টকেসের সংখ্যা নির্দেশ করে।

পরবর্তী $T$ সংখ্যক লাইনের প্রতিটিতে স্পেস দিয়ে আলাদা করে দুটি ধনাত্মক পূর্ণসংখ্যা $N$ ($ 2 \le N \le 10^4 $) এবং $X$ ($ 1 \le X \le 10^4 $) দেয়া হবে, যেগুলো উপরে বর্ণিত N ও X বোঝায়।

Output

আউটপুটে $T$ সংখ্যক লাইন থাকবে। প্রতি লাইনে তোমাকে একটি ধনাত্মক পূর্ণসংখ্যা আউটপুট দিতে হবে, যেটা প্রতিটি কেসের জন্য উপরোক্ত সমস্যার উত্তর নির্দেশ করে।

Sample

InputOutput
5
5 1
4 2
9 3
7 1
100 2
10
16
243
21
8000

Details: For the first test case

NX = 5* 1 = 5

All such positive integers M are 1, 2, 3, 4 : so that (M,N)=1 and M< NX.

Sum of these are: 1+2+3+4 =10


Submit

Login to submit.

Statistics

44% Solution Ratio
YouKnowWhoEarliest, May '20
Kuddus.6068Fastest, 0.1s
nusuBotLightest, 4.9 MB
steinumShortest, 339B
Toph uses cookies. By continuing you agree to our Cookie Policy.