575 - Skew Binary

當一數值以十進位表示時，第 k 位數表示 $10^k$ (十進制由右至左編碼，最低有效位數為第 0 位)。例如：

$81307_{10} = 8 \times 10^4 + 1 \times 10^3 + 3 \times 10^2 + 0 \times 10^1 + 7 \times 10^0 = 80000 + 1000 + 300 + 0 + 7 = 81307$

當一數值以二進制表示時，第 k 位數表示 $2^k$。例如：

$10011_2 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 16 + 0 + 0 + 2 + 1 = 19$

當一數值以 “斜偏二進制 (Skew Binary)” 表示時，第 k 位數表示 $2^{k+1} - 1$。除了最低非零的位數可能等於2之外，所有數值皆為 0 或 1。例如：

$10120_{skew} = 1 \times (2^5 - 1) + 0 \times (2^4-1) + 1 \times (2^3-1) + 2 \times (2^2-1) + 0 \times (2^1-1) = 31 + 0 + 7 + 6 + 0 = 44$

前十個斜偏二進制 (skew binary) 的數值為 0, 1, 2, 10, 11, 12, 20, 100, 101, 102。(skew binary 在某些領域特別有用，因為它使一數值加上 1 之後，最多只進位一次，但這方面的議題與本題目無關)

Input

輸入檔案有多列，每一列為一整數 n。假如 n=0 代表輸入結束，否則 n 為以斜偏二進制 (skew binary) 表示的非負整數。

Output

對每一個輸入值，輸出它的十進制表示式。n 的十進位值最大可能到 $2^{31} - 1 = 2147483647$。

Sample Input

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Sample Output

44
2147483646
3
2147483647
4
7
1041110737