题目描述

弗拉维奥·约瑟夫斯和40名叛军被罗马人围困。他的同伴们宁愿自杀也不愿投降，于是他们决定围成一个圈，每隔两人（每数到第三人时）杀死一人，绕圈执行直到无人存活。约瑟夫斯不想自杀，于是他计算出了最后存活的位置（然后他就没有自杀，因为没人能监视他了）。

我们考虑这个“游戏”的一个变种：每隔一人离开（即每数到第二人时离开）。当然，现在的人数会远多于41人，因为我们有了计算机。你需要计算出安全位置。请注意，我们可能会用你的程序来计算本次比赛的获胜者！

输入格式

输入包含多个测试用例。每个用例指定一个数 ( n )，其格式为 "xyez"，含义如下：当 ( n ) 用十进制表示时，第一位数字是 ( x )，第二位数字是 ( y )，后面跟着 ( z ) 个零。其中 ( 0 \leq x, y \leq 9 )，零的个数 ( 0 \leq z \leq 6 )。保证 ( n > 0 )。最后一个测试用例后接字符串 "00e0"。

输出格式

对每个测试用例，输出一行表示最后存活者的位置。假设参与者编号为1到( n )，计数从1号开始，即第一个离开的是2号。例如，若有5人，离开顺序为2、4、1、5，最后存活者是3号。

输入输出示例

输入数据 1

05e0  
01e1  
42e0  
66e6  
00e0  

输出数据 1

3  
5  
21  
64891137  

题目来源

Ulm Local 2004