Paula's dress search

Paula is looking for the perfect pink ball dress. Her High Street has 100 shops spread evenly along both sides, odd numbers on one side and even numbers on the other, as usual.

Paula always begins at the shop nearest her home, shop 50, which sits right in the middle of the even numbered side. Every shop owner knows which shop holds the dress she wants, but they like to set her a challenge, so they have agreed to tell her only one of four things.

1. Yes, I have the perfect dress for you!
2. You are on the wrong side of the road, cross over.
3. You need to look down this side of the street (amongst the lower numbered shops).
4. You need to look up this side of the street (amongst the higher numbered shops).

On answer 1 Paula buys the dress and goes home. On answer 2, 3 or 4 she walks to the middle shop of the block she now has to search. If that block holds an even number of shops, she goes to the lower numbered of the two middle shops. After answer 2 the new block is all 50 shops on the other side of the road. The owner of the shop she enters gives her one of the four answers again, and Paula carries on the same way while she needs to.

The input is a sequence of scenarios. Each scenario is a single integer on a line of its own, the number of the shop where Paula will find her perfect pink ball dress. This value is between $1$ and $100$ inclusive.

The last line of the input holds a single $0$. That line is not processed.

For each scenario print a single integer on a line of its own. The integer is the number of shops Paula had to visit in order to buy her dress.