The Easiest Problem

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

5
5 1
4 2
9 3
7 1
100 2

10
16
243
21
8000