Masud and Layla are good friend. At the age of 20, Masud went abroad to study. That's why Layla is very disappointed. So she decided to meet with Masud as soon as possible. But Layla does not know where is Masud. So she went out to find Masud.

Layla will start looking for Masud from the 1^st index. Layla know the value of n and k. Layle will go to (1+i×k)th index (where i = 0, 1, 2, 3 ... 10¹⁸) for find Masud and buy gift.

From (1+i×k)th index she will collect the gift. The price of the gift is (1+i×k) % n; ('%' means MODULO).

She will buy different priced gift. (NB: Don't buy gifts of the same price more than once.)

Laila is weak in math. So Fuad and Imran will help her to calculate the total cost of the gift.

Example:

Let's say the number n = 6 and k = 3.

Now Layla can go to (1+i×k)th index... (i = 0, 1, 2, 3, 4, 5 ... Infinity)

that's mean she will go index = 1, 4, 7, 10, 13, 16 ... Infinity. Then the cost of:

• 1^st index price is (1%6) = 1.
• 2^nd index price is (4%6) = 4.
• 3^rd index price is (7%6) = 1.
• 4^th index price is (10%6) = 4.
• ... and so it will continue.

At the end of the process, she will collect 1 and 4 cost prices gift. So the sum of all distinct price is 5.

Input

You are given n and k, where (1 <= n <= 10^9 and 1 <= k <= 10^9).

Output

An integer number in one line. Total cost of distinct gifts.

Example

Input:
6 3

Output:
5