폴라의 드레스 찾기

폴라는 완벽한 분홍색 무도회 드레스를 찾고 있다. 폴라가 사는 하이 스트리트에는 가게 100개가 길 양쪽에 고르게 늘어서 있고, 흔히 그렇듯 한쪽은 홀수 번호, 반대쪽은 짝수 번호다.

폴라는 언제나 집에서 가장 가까운 50번 가게에서 탐색을 시작한다. 50번은 짝수 번호 쪽의 한가운데에 있다. 가게 주인들은 폴라가 원하는 드레스가 어느 가게에 있는지 모두 알지만, 폴라에게 문제를 내고 싶어서 다음 네 가지 중 하나만 알려주기로 약속했다.

1. 그래, 네가 찾던 완벽한 드레스가 우리 가게에 있어!
2. 길을 잘못 골랐어. 건너편으로 건너가.
3. 이쪽 길에서 번호가 더 작은 가게들을 살펴봐.
4. 이쪽 길에서 번호가 더 큰 가게들을 살펴봐.

1번 답을 들으면 폴라는 드레스를 사서 집으로 돌아간다. 2번, 3번, 4번 답을 들으면 폴라는 이제 탐색해야 하는 가게 구간의 한가운데 가게로 간다. 구간에 속한 가게 수가 짝수이면 가운데 두 가게 중 번호가 작은 쪽으로 간다. 2번 답을 들었을 때 새 탐색 구간은 건너편 길의 가게 50개 전체다. 새로 들어간 가게의 주인이 다시 네 답 중 하나를 주고, 필요하면 폴라는 같은 방식으로 탐색을 이어간다.

입력은 여러 시나리오로 이루어진다. 각 시나리오는 한 줄에 정수 하나로 주어지며, 폴라가 완벽한 분홍색 무도회 드레스를 찾게 될 가게의 번호다. 이 값은 $1$ 이상 $100$ 이하다.

입력의 마지막 줄에는 $0$ 하나가 주어진다. 이 줄은 처리하지 않는다.

시나리오마다 정수 하나를 한 줄에 하나씩 출력한다. 이 정수는 폴라가 드레스를 살 때까지 들어간 가게의 수다.