Fwb and the Dark Chocolate

Fwb loves eating dark chocolate. He keeps his chocolate in a special box. However, today the box is empty – which means Fwb has to go out and buy some chocolate. But Fwb is health‐conscious: he will buy exactly enough chocolates to eat for exactly (a) days – no more, no less.

His eating pattern is very regular. On the first day he eats 1 chocolate; on the second day he eats 2 chocolates; in general, on the (i)th day he eats (2^{i-1}) chocolates (for (i > 0)). However, Fwb follows an additional rule: while he still has enough chocolates to follow his plan for the day he will eat, but if after finishing a day there are some chocolates left which are insufficient for the next day’s planned amount, he will stop the current pattern and restart the next day as if beginning anew – with the plan of 1 chocolate on that day, 2 on the next, 4 on the following day, etc.

More precisely, suppose that at the start of a (sub)process (called a segment) there are (Y) chocolates. Fwb will try to eat as follows:

• Day 1 of the segment: if (Y \ge 1) he eats 1 chocolate, leaving (Y-1) chocolates. Then he checks if the leftover is less than (2^1=2). If so and if some chocolates remain (i.e. (Y-1 > 0)), he ends the segment and restarts his pattern the next day.
• Otherwise, he continues: on day 2 of the segment, he will eat (2) chocolates (since the pattern is doubling), so that if after day 2 the remaining chocolates (Y-3) are less than (2^2=4) he ends the segment.
• In general, if on day (i) of the segment he eats (2^{i-1}) chocolates and the remaining chocolates (k) satisfy (k < 2^i), then the segment ends and, if (k>0), Fwb will start a new segment the very next day with the same rule (starting with 1 chocolate on that day).

The whole process continues until Fwb has finished all the chocolates. Note that in each segment the number of days is determined by the fact that the starting amount (Y) falls into the interval ([2^m-1,; 2^{m+1}-1)) for some (m); in that segment he eats for exactly (m) days and uses exactly (2^m-1) chocolates.

Your task is: Given (a) (the total number of days Fwb must eat), compute the minimum number (N) of chocolates Fwb must buy so that, following his rules, he eats chocolate on exactly (a) days.

inputFormat

The input consists of a single integer (a) ((1 \le a \le \text{a reasonable limit})) which is the total number of days Fwb will eat chocolate.

outputFormat

Output the minimum number of chocolates Fwb must buy so that, following his eating rules, he eats chocolate on exactly (a) days.

sample

1

1