위기일발

플라비우스 요세푸스와 그의 동료 반란군 40명이 로마군에게 포위되어 궁지에 몰렸다. 동료들은 항복하느니 자결하기로 뜻을 모았고, 원을 이루어 서서 세 번째 사람마다 차례로 처형하며 아무도 남지 않을 때까지 원을 돌기로 했다. 스스로 목숨을 끊고 싶지 않았던 요세푸스는 마지막까지 살아남는 위치를 미리 계산해 두었다(그리고 지켜보는 사람이 아무도 없었으므로 자결하지 않았다).

여기서는 두 번째 사람마다 원에서 빠지는 변형 게임을 다룬다. 이제는 컴퓨터가 있으므로 참가자는 41명보다 훨씬 많을 수 있다. 안전한 위치를 계산하라. 여러분의 프로그램으로 이 대회의 우승자를 계산하게 될지도 모르니 조심하라!

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 게임에 참가하는 사람 수 $n$을 나타낸다. 난이도를 높이기 위해 $n$은 항상 xyez 형식으로 주어진다. 의미는 다음과 같다: $n$을 십진수로 적었을 때 첫 번째 자리 숫자가 $x$, 두 번째 자리 숫자가 $y$이며, 그 뒤에 $0$이 $z$개 붙는다. 즉 $n = (10x + y)\cdot 10^z$이다. 범위는 $0 \le x, y \le 9$이고 $0$의 개수는 $0 \le z \le 6$이다. $n > 0$임이 보장된다. 마지막 테스트 케이스 다음에는 문자열 00e0이 온다.

각 테스트 케이스마다 살아남는 사람의 위치를 한 줄에 출력한다. 참가자는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 세기는 1번 사람부터 시작한다. 따라서 가장 먼저 빠지는 사람은 2번이다. 예를 들어 원에 5명이 있으면 $2, 4, 1, 5$ 순서로 빠지고 3번이 살아남는다.