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;
ll n;
vector<int> v;
bool vis[150000];
void getprime(){
    memset(vis,true,sizeof(vis));
    for(int i=2;i<150000;i++){
        if(vis[i]){
            v.push_back(i);
            for(int j=i;j<150000;j+=i) vis[j]=false;
        }
    }
}
int main(){
    scanf("%I64d",&n);
    getprime();
    if(n==0) return 0;
    if(n==1){
        printf("0\n");
        return 0;
    }
    if(n%2==0){
        printf("%d\n",n/2);
        return 0;
    }
    for(int i=0;i<v.size();i++){
        if(n%v[i]==0){
            printf("%I64d",(n-v[i])/2+1);
            return 0;
        }
    }
    printf("1\n");
    return 0;
}
