Pascal Loop Output

Time limit1sMemory limit128 MB

Summary

Given N up to 1e9, simulate finding the largest divisor of N smaller than N by scanning downward, and output how many steps that takes without brute force.

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

Problem

The following Pascal code reads a natural number N and prints the value of counter.

readln(N);
counter := 0;
for i := N-1 downto 1 do begin
    counter := counter + 1;
    if N mod i = 0 then break;
end;
writeln(counter);

The loop starts with i = N - 1 and decreases i by 1 until it reaches 1. In each iteration, it first increases counter by 1. Immediately after that, if i divides N, the loop stops.

Given N, determine the value printed by this code.

Input

The first line contains a natural number N.

1 <= N <= 10^9

Output

Print the value of counter printed by the code.

Examples3

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
10
```
Expected output
```
5
```
Example 3
Input
```
27
```
Expected output
```
18
```