G. Genealogy of aliens
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The planet Venus is known for its toxic atmosphere and infernal temperatures, where apparently any civilization would be unable to live and thrive. However, records of an ancient civilization (the "Venirics") that inhabited Venus millions of years ago have been recently detected on this planet.

Faced with this surprising discovery, the Union of Solar Planets (USP) decided to send to this planet the only specialist capable of retrieving these records and revealing more details about the history of the Venutian civilization: the space archaeologist Otávio.

In his extensive research, Otávio discovered surprising facts about the generations of Venirics:

  • Generation $$$0$$$ of the Venirics was composed of exactly $$$a \geq 1$$$ inhabitants.
  • In the life cycle of a Veniric capable of reproduction, they have exactly $$$r \gt 1$$$ offspring through asexual reproduction. The value of $$$r$$$ is the same for Venirics of any generation. That is, if all $$$a$$$ Venirics from generation $$$0$$$ were capable of reproduction, then generation $$$1$$$ was composed of exactly $$$ar$$$ Venirics, and so on.
  • Due to a genetic reason still unexplained, all individuals of a certain generation $$$m \geq 0$$$ were unable to reproduce, but all individuals up to the previous generation were capable of reproduction. Thus, the Venirics civilization ended after the death of individuals from generation $$$m$$$.

The only intact record that Otávio found about the size of the historical Venirics population was its total number (i.e., the sum of the sizes of all populations from generation $$$0$$$ to generation $$$m$$$), but he was unable to deduce anything about the values of $$$a$$$, $$$r$$$, and $$$m$$$, and therefore asked for help from Marcelo, the space computer scientist.

Marcelo was also unable to deduce the values of $$$a$$$, $$$r$$$, and $$$m$$$ from $$$n$$$, as he wisely noticed that different values of these parameters could have led to the same value of $$$n$$$. The only thing he knows is that there are not many possibilities for the sizes of the generations given $$$n$$$, and he wishes to determine how many there are.

Since returning from the toxicity of Venus, however, he can no longer type, and so he asked you to write a program that answers the question for him.

Input

A single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the total historical population of the Venirics.

Output

A single positive integer $$$t$$$, the number of possibilities for the sizes of the Veniric generations that would have made the total historical population of Venirics equal to $$$n$$$.

Examples
Input
7
Output
3
Input
1000000000
Output
101
Note

For $$$n=7$$$, the $$$3$$$ possibilities for the sizes of the generations are:

  • Generation $$$0$$$ with $$$7$$$ inhabitants who did not reproduce.
  • Generation $$$0$$$ with $$$1$$$ inhabitant who reproduced and had $$$6$$$ offspring ($$$r=6$$$), and generation $$$1$$$ with $$$6$$$ inhabitants who did not reproduce.
  • Generation $$$0$$$ with $$$1$$$ inhabitant who reproduced and had $$$2$$$ offspring ($$$r=2$$$). Generation $$$1$$$ with $$$2$$$ inhabitants who reproduced, each having $$$2$$$ offspring. Generation $$$2$$$ with $$$4$$$ inhabitants who did not reproduce.