Trừ ước nguyên tố

Cho số nguyên $n$. Áp dụng thuật toán sau:

1. Nếu $n=0$, kết thúc.
2. Tìm ước số nguyên tố nhỏ nhất $d$ của $n$.
3. Trừ $d$ khỏi $n$, quay lại bước 1.

Hãy đếm số lần trừ thuật toán thực hiện.

Dữ liệu vào

Một dòng chứa số nguyên $n$ ($2\le n\le {10}^{10}$).

Dữ liệu ra

In ra số lần trừ.

Ví dụ