Yule Lads

The children of Iceland are lucky. They do not have just one Santa Claus, they have $N$ of them! They are called the Yule Lads, and on each of the $N$ nights before Christmas one of them comes to town, bringing a small gift to children who have been nice and a potato to children who have been naughty.

On a street in a small Icelandic town there are $N$ houses, numbered from $1$ to $N$. Every house is beautifully decorated with Christmas lights, and in the beginning all the lights are on.

On each of the $N$ nights before Christmas, one of the Yule Lads visits this street. The Yule Lad who visits $K$ nights before Christmas is very fond of the number $K$, so he only visits houses whose number is a multiple of $K$. The Yule Lads are also troublemakers: in every house they visit they toggle the Christmas lights, turning them off if they are on and on if they are off.

But some of the Yule Lads felt sick and never came to town. On Christmas day the lights of every house except house $1$ were on. How many Yule Lads came to town?

An integer $p$ is a multiple of an integer $q$ when the division $p/q$ leaves no remainder.

The first line contains a positive integer $N$, the number of Yule Lads and the number of houses on the street ($1 \le N \le 10^{13}$).

Print a single integer, the number of Yule Lads that came to town. You may assume there is exactly one scenario in which every house except house $1$ has its lights on.

Consider the case $N = 6$. There are six houses on the street, and here is what happens on each of the six nights before Christmas, assuming no Yule Lad is sick.

• Six nights before Christmas, the Yule Lad turns the lights at house $6$ off.
• Five nights before Christmas, the Yule Lad turns the lights at house $5$ off.
• Four nights before Christmas, the Yule Lad turns the lights at house $4$ off.
• Three nights before Christmas, the Yule Lad turns the lights at house $3$ off and the lights at house $6$ on.
• Two nights before Christmas, the Yule Lad turns the lights at houses $2$ and $6$ off and the lights at house $4$ on.
• The night before Christmas, the Yule Lad turns the lights at houses $1$ and $4$ off and the lights at houses $2$, $3$, $5$ and $6$ on.

But then house $4$ would have its lights off on Christmas day, contrary to what actually happened.

If instead only the Yule Lad due four nights before Christmas is sick, then every house except house $1$ has its lights on on Christmas day. The answer is therefore $5$: the Yule Lads who came to town are the ones due $6$, $5$, $3$, $2$ and $1$ nights before Christmas.