Cho ba số tự nhiên \(N, K\) và \(D\). Hãy đếm xem có bao nhiêu số tự nhiên \(A\) thoả mãn:

• \(1 \le A \le N\);
• \(A \times K\) chia hết cho \(D\).

Input

Dữ liệu nhập vào từ bàn phím gồm ba dòng:

• Dòng đầu tiên là số tự nhiên \(N (1 \le N \le 10^{15})\).
• Dòng thứ hai là số tự nhiên \(K (1 \le K \le N)\)
• Dòng đầu tiên là số tự nhiên \(D (1 \le D \le 6)\).

Output

• In ra màn hình một số duy nhất là số lượng số \(A\) thoả mãn yêu cầu đề bài.

Example

10
4
6

3

20
5
1

20