Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Easiest Problem

By Tareq_Abrar · Limits 1s, 512 MB

Tareq Abrar is a lazy programmer. He has a friend named Aminvai, who is famous for his amazing skills. Aminvai has a lot of followers & a fan club. Once, Tareq gave him a problem to solve. But Aminvai was busy with his newly married wife. So, Tareq was very sad finding no way to solve the problem. Actually, it was very easy task. But Tareq Abrar is a lazy boy. So he told you to solve the problem. If you solve the problem, you will be considered as a helpful friend of Tareq. So, let’s help Tareq.

You will be given two positive integers $N$ and $X$. You have to observe all positive integers M so that $M<NX$ and M, N are relatively prime. If N and X are given, you’ve to answer the sum of all such M positive integers.

Two positive integers A and B are called relatively prime if $GCD(A, B) = 1$.

So, this is very easy problem. I think you will be able to help our lazy friend Tareq. 🙂

Input

There are several test cases. The first line of input contains a positive integer $T$ ($ 1 \le T \le 5 \times 10^5 $) , which denotes the number of test cases.

In each line of next $T$ lines, there will be given two positive integers $N$ ($ 2 \le N \le 10^4 $) and $X$ ($ 1 \le X \le 10^4 $) separated by space.

Output

Output will contain $T$ lines. In each line, you have to print a positive integer which denotes the answer.

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


Discussion

Statistics


32% Solution Ratio

YouKnowWhoEarliest, 3w ago

YouKnowWhoFastest, 0.1s

YouKnowWhoLightest, 7.3 MB

jubayer_khanShortest, 392B

Submit

Login to submit

Editorial

Happy Coding!!

Related Contests