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 ≤ x ≤ N) sao cho gcd(x, N) = p. Ở đây 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 ≤ 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 ≤ 1000.
• Subtask 2 (50% số điểm): N ≤ 10^6.

Example

6 2

2