ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Negotiations with Parthians

Time limit: 0.5 second
Memory limit: 64 MB
Ancient Greeks and Romans thought that gods of the underworld like even numbers, and the gods who protect the ones who were alive like odd ones. In 123 B.C., Rome was threatened by the war with Parthian Empire. The emperor Adrian did not want the bloodshed; therefore he went to carry the negotiation with parthians. In order get the gift of great eloquence from the gods, he wanted to sacrifice a herd of n sheep. Of course, n was an odd number. Thinking about that, Adrian realised that he should give the equal number of sheep as a sacrifice to each of the gods. Otherwise, a god who gets less sheep than some other god becomes furious at Adrian, and this might prevent him to solve the problem in the peaceful way.
The emperor called for Theon of Smyrna, the mathematician, and ordered him to divide sheep equally. Theon of Smyrna was also superstitious, that's why he thought that the amount of gods not only should be odd, but also should have odd amount of positive divisors. Apparently, he was able to solve the problem and negotiations with Parthia finished successfully. Can you solve this problem?


The only line contains an integer odd number n that is a total amount of sheep to sacrifice (1 ≤ n ≤ 1018 − 1).


Output the number of gods to receive a sacrifice. If this problem has several answers, output the maximal one.


Problem Author: Grigoriy Nazarov
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1854. Negotiations with Parthians