Problem Description

This problem is a translation from CCC 2018 S4「Balanced Trees」

We define a "perfect balanced tree" as follows:

Every perfect balanced tree has a positive integer weight. A perfect balanced tree with a weight of $1$ is a tree with only one node. Otherwise, the tree has a weight of $w (w \ge 2)$, and it is a rooted tree with $k (2 \le k \le w)$ subtrees. All $k$ subtrees must be identical, and each of them must be perfectly balanced.

Specifically, all $k$ subtrees must have the same weight, which must be $\left\lfloor\frac{w}{k}\right\rfloor$. For example, if a perfect balanced tree with a weight of $8$ has $3$ subtrees, then each subtree has a weight of $2$, because $2 + 2 + 2 = 6 \le 8$.

Given $N$, find the number of perfect balanced trees with a weight of $N$.

Input Format

The input contains a single line with an integer $N$.

Output Format

Output a single integer representing the number of perfect balanced trees with a weight of $N$.

Sample Input and Output

Sample Input #1

4

Sample Output #1

3

Sample Input #2

10

Sample Output #2

13

Notes

Sample Explanation 1

The valid trees are:

• A perfect balanced tree with $4$ subtrees each of weight $1$;
• A perfect balanced tree with $2$ subtrees each of weight $2$;
• A perfect balanced tree with $3$ subtrees each of weight $1$.

For $33\%$ of the data, $N \le 1000$;
For another $13\%$ of the data, $N \le 5 \times 10^4$;
For another $13\%$ of the data, $N \le 10^6$;
For all data, $1 \le N \le 10^9$.

见题面 Input 部分

见题面 Output 部分