Cho \(3\) số nguyên dương \(x, n, m\). Hãy đếm xem có bao nhiêu số nguyên dương \(y\) thỏa mãn:

• \(y\le n\)
• \(x \times y\) chia hết cho \(m\)

Yêu cầu: Cho trước \(x, n, m\), hãy lập trình tìm số lượng số \(y\) thỏa mãn.

Input

• Một dòng chứa \(3\) số \(x, n, m ( x, n, m\le 10^{16})\).

Output

• Một số nguyên là số lượng số nguyên \(y\) thỏa mãn yêu cầu của bài toán.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^4\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^8\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

6 13 8

3