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<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// gp_hash_table<int, int> table;

#define ll long long
#define vii vector< ll >
#define pb push_back
#define pii pair<ll,ll>
#define vec(a) vector<a >
#define se second
#define fi first
#define ins insert

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define MD          1000000007
#define M 			300011
#define LN 			124
#define fftmod      998244353
#define EPS         (double)1e-10
#define PI          3.14159265358979323846264
#define swap(a,b)  {a=b+a;b=a-b;a=a-b;}

ll md=MD;

inline ll exp(ll a,ll b){ll r=1LL;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b/=2;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(a==0)return b;if(b==0)return a;return gcd(b,a%b);}
inline ll poww(ll a,ll b){ll r=1LL;while(b>0){if(b&1)r=r*a;b/=2;a=a*a;}return (ll)r;}


char a[2000];
int cnt[26][2000];
set<ll> st;
ll check(ll i,ll j,ll k){
	if(st.size()==0)return 1;
	ll p=0;
	for(auto x:st){
		p+=(cnt[x][j]-cnt[x][i-1]);
	}
	if(p<=k)return 1;return 0;

}
ll f(ll i,ll k,ll n){
	ll p=n,x=i-1;
	for(;p>=1;p/=2){
		while(p+x<=n&&check(i,x+p,k))x+=p;
	}
	return x-i+1;
}
int main(){


#ifndef ONLINE_JUDGE
	double _tBeg=clock();
#endif

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t,i,s,j,m,z,x,y,k,n,p,q,T;string s1,s2,s3;x=1;
    cin>>n;p=0;
    for(i=2;i<=1e6;++i){
    	if(n%i==0){
    		p=1;
    		n-=i;
    		break;
    	}
    }
    if(!p)cout<<-1,exit(0);
    	p+=n/2;cout<<p;










 
#ifndef ONLINE_JUDGE
    double _tEnd=clock();
    printf("\ntotal time %.6f\n",(_tEnd-_tBeg)/CLOCKS_PER_SEC);
#endif
    return 0;

}