Description

当我们要用十进制数表达二进制数的时候，使用如下的实例转换：

100112＝124+023+022+121+1*20

＝16+0+0+2+1

＝19

可是，有一种另类的二进制数，虽然也是逢2进位，但其允许各位上其中有一个可以是2，其成数的规则暂且不论，它到十进制数的转换却以如下的实例说明：

101202’＝1(25-1)+0(24-1)+1(23-1)+2(22-1)+0*(21-1)

＝31+0+7+6+0

＝44

该另类二进制数的前10个数为0, 1, 2, 10, 11, 12, 20, 100, 101, 102，显然与3进制数不同，它的增1操作是以先消去存在的2为前提的，即将2变成0，而直接进位。若所有的位都是0或1，它才从个位开始增值。因此，这种数的操作优点是，加1时最多只有一次进位，因而在某些应用上很有用。

你的任务是编程将另类二进制数转换成十进制数。 　

Input

输入数据中有一些行，每行中有一个数（位长≤31），若为0，则表示输入结束，否则就表示非负的另类二进制数。

Output

对于每个另类二进制数，输出其等价的十进制数，其十进制数最大不会超过2^31-1。

Sample

Input

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Output

44
2147483646
3
2147483647
4
7
1041110737