The Major-Domo's Brain-Buster
In the roadside tavern where the pilgrims paused, the majordomo, a clever and well-educated man, noticed several rounds of cheese of varying sizes. Inspired by this sight, he decided to entertain the travelers with a puzzle. He requested four stools and arranged eight rounds of cheese on the farthest stool, as depicted in the image.
- "Here's a riddle," he announced, "that I once challenged my friends from Boldswell in Norfolk with. I swear by Saint Joseph, not one of them could solve it! Yet it is quite simple. Your task is to move all the cheeses from one stool to the stool at the opposite end. However, you must never place a larger round of cheese on top of a smaller one. Whoever accomplishes this in the fewest moves will be treated to a sip of the finest wine our gracious host offers."
What is the minimum number of moves required to solve the majordomo's puzzle? And how swiftly can you achieve it?
Input
Each line of the input file contains a single number n (1 ≤ n ≤ 255) - representing the number of cheeses on the first stool. Continue reading the input data until the end of the file.
Output
For each number provided in the input, output a single number on a separate line - the solution to the majordomo's puzzle.