Hide

Problem G
Integer Estate Agent

After recent riots in Flatland, the leader has granted permission to purchase real estate at the famous Zero street to everyone. Now, not only the noble polygons are allowed to live there, but pentagons, squares, and even triangles as well (if they can afford a house at Zero street, of course)!

As an employee of the “Integer Estate Agency,” you are in charge of the one side of the street. House numbering starts right after Zero Square. House #$1$ is right off of the square, House #$2$ comes right after House #$1$, House #$3$ comes after House #$2$, and so on towards Infinity (where, as rumors say, the family of noble Perfect Circles live). House #$k$ costs exactly $k+1$ coins. There is no House #$0$, since that is the square.

A promising customer is willing to spend exactly $n$ coins to purchase a single block of consecutive houses to group together as a condo complex. How many options does he have? For example, if he wishes to spend $5$ coins, he may buy houses #$1$ and #$2$ (which costs $2+3=5$), or he may just buy house #$4$, so he has two options.

Input

There will be up to $50\, 000$ test cases in the input. Each test case will consist of a single integer $n$ ($1 \le n \le 1\, 000\, 000$) on its own line, indicating the number of coins a customer is willing to spend. The input will end with a line with a single 0.

Output

For each customer, output the number of ways he can buy consecutive houses spending exactly $n$ coins.

Sample Input 1 Sample Output 1
1
2
5
0
0
1
2

Please log in to submit a solution to this problem

Log in