CF1076B Divisor Subtraction

You are given an integer number $ n $ . The following algorithm is applied to it: 1. if $ n = 0 $ , then end algorithm; 2. find the smallest prime divisor $ d $ of $ n $ ; 3. subtract $ d $ from $ n $ and go to step $ 1 $ . Determine the number of subtrations the algorithm will make.

The only line contains a single integer $ n $ ( $ 2 \le n \le 10^{10} $ ).

Print a single integer — the number of subtractions the algorithm will make.

In the first example $ 5 $ is the smallest prime divisor, thus it gets subtracted right away to make a $ 0 $ . In the second example $ 2 $ is the smallest prime divisor at both steps.