ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

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?

### 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
To submit the solution for this problem go to the Problem set: 1854. Negotiations with Parthians