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.
/*.Youtube channel: Upsolve 2.0. */
/*....Instagram : _jais.sat_.... */
/*...... Ask your doubts........ */
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define dbl long double
#define _tc long long int T;cin>>T;while(T--)
#define GET(_1,_2,_3,_4,NAME,...) NAME
#define nl(...) GET(__VA_ARGS__, nl4, nl3, nl2, nl1)(__VA_ARGS__)
#define nl1(a) lli a;cin>>a;
#define nl2(a,b) lli a,b;cin>>a>>b;
#define nl3(a,b,c) lli a,b,c;cin>>a>>b>>c;
#define nl4(a,b,c,d) lli a,b,c,d;cin>>a>>b>>c>>d;
#define nc(a) char a;cin>>a;
#define rep(i,s,a) for(lli i=s;i<=a;i++)
#define per(i,s,a) for(lli i=s;i>=a;i--)
#define rep0(i,a) for(lli i=0;i<a;i++)
#define rep1(i,a) for(lli i=1;i<=a;i++)
#define _fill(x) for(auto &X:x) cin>>X;
#define _v(x) vector<x>
#define _vv(x) vector<vector<x>>
#define _p(a,b) pair<a,b>
#define _m(a,b) map<a,b>
#define _t(a,b,c) tuple<a,b,c>
#define _s " "
#define pb push_back 
#define mp make_pair
#define fir first
#define sec second
#define yes "YES\n"
#define no "NO\n"
#define lc "\n"
#define elif else if
#define mod 1073741824
#define _max 100000000000000000
#define _min -100000000000000000
#define pie 3.1415926536
#define hi cout<<"hi";
#define setdeci(a) fixed<<setprecision(a)
#define _sqr(x) ((x)*(x))
#define setbit(x) __builtin_popcount(x)
#define INP freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define _lb(x,v) lower_bound(all(x),v)
#define _ub(x,v) upper_bound(all(x),v)
//#define _pow(a,b) ((lli)(pow(a,b)+0.5))
#define _disp(a,b) for(auto x:a){cout<<x<<b;}
#define _mat(Data,Row,Col,Val,Name) _v(_v(Data)) Name(Row,_v(Data)(Col,Val));
#define _auto(z) for(auto &_x:z)
lli dx[]={0,1,0,-1},dy[]={1,0,-1,0};
lli dxx[]={-1,0,1,1,1,0,-1,-1},dyy[]={-1,-1,-1,0,1,1,1,0};
bool _palin(string s){for(lli i=0,j=s.length()-1;i<=j;i++,j--){if(s[i]!=s[j])return 0;}return 1;}
bool by_second(auto a,auto b){return a.sec<=b.sec;}
lli _prime(lli n){if(n<=1)return 0;if(n<=3)return 1;if(n%2==0||n%3==0)return 0;for(lli i=5; i*i<=n; i=i+6)if (n%i == 0 || n%(i+2) == 0)return 0;return 1;}
lli _fact(lli a){ return (a==1||a==0)?1:(a*_fact(a-1));}
lli _lcm(lli a, lli b){return a / __gcd(a, b) * b;}
dbl _dist(lli x1,lli y1,lli x2,lli y2){return sqrt(pow(x2 - x1, 2)+pow(y2 - y1, 2) * 1.0);} 
lli _digsum(lli n){lli s=0;while(n>0){s+=n%10;n/=10;}return s;}
lli _pow(lli x,lli y){ lli temp;if( y == 0) return 1LL;temp = _pow(x, y/2);if (y%2 == 0) return temp*temp; else return x*temp*temp;}
lli _invmod(lli x,lli y,lli m){if (y == 0) return 1; lli p =_invmod(x, y / 2, m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m;}
bool comp(_p(lli,string) a,_p(lli,string) b)
{ return (a.fir<b.fir);}
int main(void)
{FAST
 
 nl(n);
 lli ans=0;
 if(_prime(n))
 cout<<1<<lc;
 elif(n%2==0)
 {
 	cout<<n/2<<lc;
 }
 else
 {
 	for(lli i=3;n>0;i+=2)
 	{
 	  if(_prime(i))
 	  {
 		cout<<n/i<<lc;break;
 	  }
 	}
 	

 }
 return 0;
}


    
 

    
    
    
    
    
    
    
    