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 fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define sorta(v) sort(v.begin(),v.end())
#define sortd(v) sort(v.begin(),v.end(),greater<>())
#define mkp make_pair
#define endl "\n"
#define tab " "
#define pb push_back
#define ff first
#define ss second
#define gcd __gcd
#define all(c)  c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define tc ll T;cin>>T;while(T--)
#define inf (long long)9e18
const ll mod = 1e9 + 7;
const ll N = 1e7;
ll powm(ll x, ll y, ll p)  {  ll res = 1; x = x % p; while (y > 0) {if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p;}   return res; }
ll lcm(ll x,ll y){return (x*y*1LL)/gcd(x,y);}
ll pow(ll x, ll y) { ll res = 1; while (y > 0) { if (y & 1) res = ((res) * (x)); y = y >> 1; x = ((x) * (x)); } return res; }
void solve()
{
	ll n;
	cin>>n;
	ll i;
	if(n%2==0)
	{
		cout<<n/2;
	}
	else
	{
		for(i=3;i<=(sqrt(n));i++)
		{
			ll p=1,flag=0;
			if(n%i==0)
			{
				p=i;flag=1;
			}
			if(flag)
			{
				cout<<(n-p)/2 + 1;
				break;
			}
		}
	}
	
	
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("billboard.out", "w", stdout);
	#endif
	fast
	//tc
	solve();
}