Cho 2 số ~a~ và ~m~ . Hãy đếm xem có bao nhiêu số nguyên dương ~k~ thỏa mãn ~ 0 \le k < m ~ . Mà ~ \gcd(a+k,m) = \gcd(a,m) ~ .

Chú ý: ~ \gcd(a,b) ~ là ước chung lớn nhất của 2 số a,b.

Input

Gồm 1 dòng chứa 2 số nguyên dương ~ a,m ~ (~ 1\le a < m \le 10^{10} ~ ).

Output

In ra kết quả bài toán

Sample

Input #1

3 5

Output #1

4

Hint

Trong ví dụ trên có tất cả 4 số là : 0,1,3,4