Skew Binary

When a number is written in decimal, the $k$-th digit (counting from the right, with the least-significant digit numbered $0$) represents a multiple of $10^k$. For example,

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

When a number is written in binary, the $k$-th digit represents a multiple of $2^k$. For example,

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

In skew binary, the $k$-th digit represents a multiple of $2^{k+1} - 1$. The only allowed digits are $0$ and $1$, except that the least-significant nonzero digit may be a $2$. For example,

$10120_{\text{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$

The first $10$ numbers in skew binary are $0, 1, 2, 10, 11, 12, 20, 100, 101,$ and $102$. (Skew binary is useful in some applications because you can add $1$ with at most one carry. However, that has nothing to do with this problem.)

The input consists of one or more lines, each containing a single integer $n$. If $n = 0$, it signals the end of the input; otherwise $n$ is a nonnegative integer written in skew binary. The decimal value of $n$ is at most $2^{31} - 1 = 2147483647$.

For each number, output its decimal equivalent on its own line.