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>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fast ios::sync_with_stdio(0);cin.tie(NULL);std::cout.tie(NULL);
#define endl "\n"
#define vst vector<char>
#define vll vector<ll>
#define fo(i, x, y)   for (__typeof(x) i = x; i < y; ++i)
#define fr(i, x, y)   for (__typeof(x) i = x; i > y; i--)
#define sort(a) stable_sort(a.begin(),a.end())
#define sortd(a) stable_sort(a.begin(),a.end(),greater<int>())
#define vpr vector<pair<ll,ll>>
#define gcd(a,b) __gcd(a,b)
#define TC ll t; cin>>t; while(t--)
#define F first
#define S second
const ll N=1e9+7;
const ll MAX=1e5;
const ll MIN=-1e5;
ll lcm(ll x,ll y){return (x*y*1LL)/gcd(x,y);}
 
ll power(ll x, ll y){ 
    ll res = 1; 
    while (y > 0){
        if (y & 1) 
            res = ((res) * (x));
        res %= N; 
        y = y >> 1; 
        x = ((x) * (x)); 
    }
    return res; 
}
 
ll powmod(ll x, unsigned ll y, ll p) 
{ 
    ll res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
 
ll fact(ll n, ll p) {
    ll res = 1;
    while (n > 1) {
        res = (res * ((n/p) % 2 ?  p-1 : 1)) % p;
        for (ll i = 2; i <= n%p; ++i)
            res = (res * i) % p;
        n /= p;
    }
    return res % p;
}
vll a;

void SieveOfEratosthenes(ll n) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (ll p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (ll i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (ll p=2; p<=n; p++) 
       if (prime[p]) 
          a.pb(p);
} 
  

int main()
{
   fast;
  // ll t;cin>>t;
   
  // while(t--)
   //{
       ll n;
       cin>>n;
       ll val=sqrt(n);ll ans;
           SieveOfEratosthenes(100000);
           if(n%2==0)
           cout<<n/2<<endl;
           else
           {ll f=0;
           fo(i,1,a.size())
           {
               if(n%a[i]==0)
               {
                   f=1;
                   n-=a[i];
                   ans=n/2+1;
                   break;
               }
           }
           if(f==1)
          cout<<ans<<endl;
          else cout<<n<<endl;

           }


      
       
    
   
}  