Bạn được cung cấp một số nguyên dương \(N\).

Nhiệm vụ của bạn là đếm số lượng số nguyên dương \(x(1 \le x \le N)\) sao cho \(gcd(x,N) = p\).

\(gcd(a,b)\) là ước chung lớn nhất của a và b.

Input

• Gồm hai số nguyên dương \(N\) và \(p\) \((p \le N)\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 1000\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^6\).

Example

6 2

2