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.

Input

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

Output

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

Examples

Input


5


Output


1


Input


4


Output


2

Note

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.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <utility>
#include <vector>
#define INF 1e9
#define MAXN 30000
using namespace std;
typedef __int64 ll;
typedef pair<int,int> P;
int n;
vector<int> v;
bool vis[150000];
void getprime(){
    memset(vis,true,sizeof(vis));
    for(int i=2;i<150000;i++){
        if(vis[i]==true){
            v.push_back(i);
            for(int j=i;j<150000;j+=i)
                vis[j]=false;
        }
    }
}
int main(){
    scanf("%d",&n);
    if(n==0) return 0;
    if(n==1){
        printf("0\n");
        return 0;
    }
    getprime();
    int sum=0;
    for(int i=0;i<v.size();i++){
        while(n%v[i]==0){
            n/=v[i];
            sum++;
        }
        if(n==1) break;
    }
    if(n!=1) sum++;
    printf("%d\n",sum);
    return 0;
}
