Janosik

Janosik, also known as Robin Hood, takes from the rich to give to the poor. He and his gang ambushed a convoy carrying gold to the counts' castle and made off with $n$ caskets. Once the loot reached their cave they counted it: casket $i$ (for $i = 1, 2, \dots, n$) holds exactly $i$ money-bags full of gold.

When a poor man comes asking for a few gold ducats, Janosik follows this procedure. He first picks a non-empty casket that holds the fewest money-bags.

• If that casket holds exactly one money-bag, he hands it to the man, who leaves happy.
• If it holds more than one money-bag and the count is odd, he slips one money-bag into his own pocket and starts the procedure again from the beginning.
• If the count is even, he takes out exactly half of the money-bags and puts them in an empty casket (spare caskets are plentiful in the cave), then starts the procedure again from the beginning.

As long as at least one non-empty casket is left, the visitor is sure to walk away with a money-bag of gold after some number of rounds of the procedure. The poor keep coming to the cave until every casket is empty.

The other robbers wonder whether their leader is ruining the good name of thugs. They want to know how many looted money-bags stay in Janosik's pocket once all the caskets are empty.

The first and only line contains one integer $n$ ($1 \le n \le 10^9$), the number of caskets that Janosik's gang robbed.

Print the number of money-bags of gold that stay in Janosik's pocket after all the caskets are empty.