400790: GYM100247 L For the Honest Election

The presidential election is held in the state R and n citizens have the vote. Candidate P has not really enough supporters, but he has a friend in the election committee, so he proposed a new voting scheme. The election committee has two options.

In the first option each citizen votes for the one of the citizens he trusts. The citizen who has more votes than any other citizen chooses any citizen he wants as a president. Of course if the supporter of the candidate P is that elected citizen, P will be a president.

In the second option the committee divides the voters into the few groups of the same size, and the representative in every group is elected using the same scheme. That means the group can be divided again or the election described in the first option can be held. After the representatives for each group are elected they choose the representative among each other using the first option.

Candidate P is planning to use his friend from the election committee to divide the citizens into the groups by himself. Note that the supporters of the candidate P are absolutely honest with each other and for the common good they can arrange whom to vote for in each election. Now P thinks about the minimal number of supporters he should have to win the election for sure.

The only line contains one integer n (1 ≤ n ≤ 10⁹) — the number of the citizens of R who has the vote.

Output the only integer — minimal number of the supporters candidate P needs to win the election for sure.

9

4

12

6

Let's consider the first sample. P can divide 9 voters into 3 groups of 3 people. Inside each group he needs 2 votes for the loyal representative election. At the same time only 2 of 3 groups are enough for him to elect the loyal representative. Therefore he should send 2 supporters in the first group and other 2 in the second one to win the election.