# Practice on Toph

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

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

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. 🙂

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 will contain `$T$`

lines. In each line, you have to print a positive integer which denotes the answer.

Input | Output |
---|---|

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 |

32% Solution Ratio

YouKnowWhoEarliest,

YouKnowWhoFastest, 0.1s

YouKnowWhoLightest, 7.3 MB

jubayer_khanShortest, 392B

Login to submit

Happy Coding!!