Counting Consecutive Sums

Interview

Time limit2sMemory limit32 MB

Summary

Count the number of ways to express a given natural number N as a sum of one or more consecutive natural numbers.

Level: Easy3 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

You are given a natural number N. Count how many ways N can be written as the sum of one or more consecutive natural numbers.

Every number used in the sum must be a natural number between 1 and N, inclusive. For example, 15 can be written in four ways: 15, 7+8, 4+5+6, and 1+2+3+4+5. The number 10 can be written in two ways: 10 and 1+2+3+4.

Input

The first line contains an integer N.

1 ≤ N ≤ 10,000,000

Output

Print the number of ways to write N as the sum of one or more consecutive natural numbers.

Examples1

Example 1
Input
```
15
```
Expected output
```
4
```