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 ≤ 10¹⁸ − 1).

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