Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2598
Yet Another Digit

Time Limit: 2 Seconds      Memory Limit: 65536 KB

When making different calculations we usually use decimal notation. On the other side, computers usually store and process information in binary form. Both decimal and binary notations are special cases of so called base notations. Base notation is the way to represent integer number as the sum of powers of some integer number B called the base of the notation, taken with some coefficients called digits. Thus the weight of the i-th digit is proportional to Bi (digits being numbered from zero).

Most base notations that we use have a nice property - for any particular number the value of each digit is defined unambiguously. For example, consider the number 5. In binary notation the rightmost digit is 1, the next one is 0, the second digit is 1 and all the others are 0.

However, this property just follows from the fact that the number of different values for digits is equal to the base of the notation. If we allow more different values for each digit, the uniqueness of representation would be lost. Consider redundant binary notation, where three digits are allowed: 0, 1 and 2. In this notation some particular number may have several representations. For example, 5 can be represented as both 101 and 21.

Find out the number of different representations of the given number R in redundant binary notation.


Input

Input file contains several lines. In each line there is the integral number R (0 <= R <= 10100). A line with R < 0 indicates the end of input, which should not be proceeded.


Output

For each integer R, output one integer - the number of ways R can can be represented in redundant binary notation.


Sample Input

5
7
-1

Sample Output

2
1


Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6
Submit    Status