Cho hai số nguyên dương \(L, R\) và \(N\). Đếm số lượng số \(x\) trong đoạn \([L, R]\) sao cho \(\gcd(x, N) = 1\).

Định dạng đầu vào

• Một dòng chứa ba số nguyên \(L, R, N\) (\(1 \le L \le R \le 10^{12}\), \(1 \le N \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượng số thỏa mãn.

Ví dụ

Input:

1 10 6

Output:

3

Giải thích: Trong [1,10], các số nguyên tố cùng nhau với 6: 1, 5, 7.

Ràng buộc

• 100% số điểm: \(N \le 10^9\), \(R - L \le 10^6\).