Unit Squares Along a Diagonal

Time limit1sMemory limit128 MB

Problem

$R$ is a rectangle whose side lengths are integers. It can be tiled exactly by unit squares, each with side length $1$.

Define $f(R)$ as the number of unit squares that one diagonal of the rectangle $R$ passes through. For example, a rectangle with side lengths $2$ and $4$ has $f(R) = 4$.

Given a natural number $N$, count the number of rectangles $R$ that satisfy $f(R) = N$. A rectangle with side lengths $a$ and $b$ is considered the same as one with side lengths $b$ and $a$.

Input

The first line contains a natural number $N$ ($0 < N < 10^6$).

Output

Print the number of rectangles $R$ satisfying $f(R) = N$ on the first line.

Hint

Think about how to express, using only the two side lengths $a$ and $b$, the number of unit squares that the diagonal of an $a \times b$ rectangle passes through.