403554: GYM101193 E Elections

The President of Bandiaterra Mr. Barbato is preparing for the next year upcoming elections. Nowadays his rating has fallen drastically to the lowest value ever (0.42%). The staff of president administration office have realized that they have to act in order for Mr. Barbato to save his office.

There are n citizens of Bandiaterra that are eligible to vote. Each of them is assigned to a particular electoral district. The electoral districts contain the same number of citizens each. The same principle is applied to split districts to subdistricts, subdistricts to subsubdistricts, subsubdistricts to subsubsubdistricts, etc. Splitting of an administrative unit (subdistrict) is allowed as long as the number of citizens in the unit is divisible by an integer.

Traditionally there are two candidates for the president office: the current president and an opposition candidate. Each citizen of the smallest administrative unit votes directly for a delegate, which is obliged to vote for the respective candidate at the next state of the election. Thus, after several stages of the election each elective district (the largest administrative unit) is represented by a delegate, and these delegates give their votes to candidates. According to the Bandiaterra constitution, if the candidates have equal number of votes, the opposition candidate wins.

Barbato was one of the election system's designers. For this reason, only the current president has the exclusive right to form the electoral districts. It means that Barbato is allowed to specify which citizens belong to which districts, as long as the numbers of the citizens in the districts respect the rules described above. Of course, Mr. President is going to hold a huge agitation campaign to convince the compatriots to vote for him. However, he would like to be sure that he will definitely be elected for a new term. Given that he decides on the structure of districts at all levels, what is the minimum number of votes that Barbato needs to guarantee his victory?

The first line contains a positive integer number n — the number of citizens that are eligible to vote in Bandiaterra.

Output a single line containing a single number — the minimum number of votes that would guarantee a victory for Barbato.

130

42