Cho \(L, R, N\). Đếm số lượng số \(x\) trong \([L, R]\) sao cho \(\gcd(x, N) = 1\).

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

• Một dòng chứa \(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 là kết quả.

Ví dụ

Input:

1 10 6

Output:

3

Ràng buộc

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