Consecutive Sum

Time limit5sMemory limit256 MB

Summary

Given q, count how many p make the sum of p consecutive integers equal the sum of the next q consecutive positive integers. Handle up to 2000 queries with q below 10^14.

Level: Medium7 of 10
Topics: Number theory, Math, Binary search, Combinatorics
Solved: No attempts yet

Problem

There are cases where the sum of $p$ consecutive integers ( $p > 0$ ) equals the sum of the $q$ consecutive positive integers that immediately follow them.

For example, $9+10+11+12 = 13+14+15$ , so $p=4$ and $q=3$ ; and $4+5+6+7+8 = 9+10+11$ , so $p=5$ and $q=3$ .

Given $q$ , write a program that counts how many values of $p$ satisfy this condition.

Input

The input consists of several test cases. Each test case is a single line containing one integer $q$ . $q$ is a positive integer less than $10^{14}$ .

The last line of the input contains a single $0$ , which is not processed. The number of test cases does not exceed $2{,}000$ .

Output

For each test case, print the number of values of $p$ that satisfy the condition, one per line.

Examples1

Example 1
Input
```
5
1
0
```
Expected output
```
6
2
```