Wiring

Time limit1sMemory limit256 MB

Summary

Count how many distinct wires appear after N squared triangular steps join nails around a circle.

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

Problem

There are $N$ nails driven into the rim of a large circle at equal spacing. Call one of them $P_0$ , then name the rest $P_1$ through $P_{N-1}$ going clockwise.

Wires are connected by the following rule.

Let $Q_0 = P_0$ .
Repeat step $p$ from step $1$ to step $N^2$ . If $Q_{p-1} = P_k$ , set $Q_p = P_{(k+p) \bmod N}$ and join $Q_{p-1}$ to $Q_p$ with a wire. If the two nails are already joined, no new wire is added. If $Q_{p-1}$ and $Q_p$ are the same nail, no wire is added.

Find how many wires are connected once every step is done.

Input

The first line contains a natural number $N$ . ( $3 \le N \le 10^{12}$ )

Output

Print the number of connected wires on the first line.

Examples3

Example 1
Input
```
3
```
Expected output
```
1
```
Example 2
Input
```
4
```
Expected output
```
3
```
Example 3
Input
```
5
```
Expected output
```
2
```