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.
import java.util.*;
import java.math.*;

public class Main
{
    private static Scanner s;
    public static void main (String[] args){
        
        s = new Scanner(System.in);
        long num = s.nextLong();
    	
    	List<Integer> list = new ArrayList<>();
		list.add(2);
        list.add(3);
        list.add(5);
        list.add(7);
        list.add(11);
        list.add(13);
        list.add(17);
        list.add(19);
        list.add(23);
        list.add(29);
        list.add(31);
        list.add(37);
        list.add(41);
        list.add(43);
        list.add(47);
        list.add(53);
        list.add(59);
        list.add(61);
        list.add(67);
        list.add(71);
        list.add(73);
        list.add(79);
        list.add(83);
        list.add(89);
        list.add(97);
        list.add(101);
        list.add(103);
        list.add(107);
        list.add(109);
        list.add(113);
        list.add(127);
        list.add(131);
        list.add(137);
        list.add(139);
        list.add(149);
        list.add(151);
        list.add(157);
        list.add(163);
        list.add(167);
        list.add(173);
        list.add(179);
        list.add(181);
        list.add(191);
        list.add(193);
        list.add(197);
        list.add(199);
        list.add(211);
        list.add(223);
        list.add(227);
        list.add(229);
        list.add(233);
        list.add(239);
        list.add(241);
        list.add(251);
        list.add(257);
        list.add(263);
        list.add(269);
        list.add(271);
        list.add(277);
        list.add(281);
        list.add(283);
        list.add(293);
        list.add(307);
        list.add(311);
        list.add(313);
        list.add(317);
        list.add(331);
        list.add(337);
        list.add(347);
        list.add(349);
        list.add(353);
        list.add(359);
        list.add(367);
        list.add(373);
        list.add(379);
        list.add(383);
        list.add(389);
        list.add(397);
        list.add(401);
        list.add(409);
        list.add(419);
        list.add(421);
        list.add(431);
        list.add(433);
        list.add(439);
        list.add(443);
        list.add(449);
        list.add(457);
        list.add(461);
        list.add(463);
        list.add(467);
        list.add(479);
        list.add(487);
        list.add(491);
        list.add(499);
        list.add(503);
        list.add(509);
        list.add(521);
        list.add(523);
        list.add(541);
        list.add(547);
        list.add(557);
        list.add(563);
        list.add(569);
        list.add(571);
        list.add(577);
        list.add(587);
        list.add(593);
        list.add(599);
        list.add(601);
        list.add(607);
        list.add(613);
        list.add(617);
        list.add(619);
        list.add(631);
        list.add(641);
        list.add(643);
        list.add(647);
        list.add(653);
        list.add(659);
        list.add(661);
        list.add(673);
        list.add(677);
        list.add(683);
        list.add(691);
        list.add(701);
        list.add(709);
        list.add(719);
        list.add(727);
        list.add(733);
        list.add(739);
        list.add(743);
        list.add(751);
        list.add(757);
        list.add(761);
        list.add(769);
        list.add(773);
        list.add(787);
        list.add(797);
        list.add(809);
        list.add(811);
        list.add(821);
        list.add(823);
        list.add(827);
        list.add(829);
        list.add(839);
        list.add(853);
        list.add(857);
        list.add(859);
        list.add(863);
        list.add(877);
        list.add(881);
        list.add(883);
        list.add(887);
        list.add(907);
        list.add(911);
        list.add(919);
        list.add(929);
        list.add(937);
        list.add(941);
        list.add(947);
        list.add(953);
        list.add(967);
        list.add(971);
        list.add(977);
        list.add(983);
        list.add(991);
        list.add(997);
        
        long count = 0;
        int pos = 0;
        boolean div = true;
        while(num > 0){
            while(div == true){
                if(num % list.get(0) == 0){
                    count = num / 2;
                    num = 0;
                    div = false;
                }else if(num % list.get(pos) == 0){
                    num = num - list.get(pos);
                    count++;
                    div = false;
                    pos = 1;
                } else pos ++;
            }
            div = true;
        }
        System.out.println(count);
    }
}

 		 	 		  	   		 		 			 	 		 	