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

1854. 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?

Input

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

Output

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

Sample

inputoutput
45
9
Problem Author: Grigoriy Nazarov
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011