How many steps does it take from n to 1 by subtracting the greatest divisor? Inspired by this question over at Mathematics.



The Problem


  Let n be a natural number ≥ 2. Take the biggest divisor of n – which is different from n itself – and subtract it from n. Repeat until you get 1.


The Question

How many steps does it take to reach 1 for a given number n ≥ 2.

Detailed Example


  Let n = 30.


The greatest divisor of:

1.   30 is 15  --&gt;  30 - 15 = 15
2.   15 is  5  --&gt;  15 -  5 = 10
3.   10 is  5  --&gt;  10 -  5 =  5
4.    5 is  1  --&gt;   5 -  1 =  4
5.    4 is  2  --&gt;   4 -  2 =  2
6.    2 is  1  --&gt;   2 -  1 =  1


It takes 6 steps to reach 1.

Input


Input is an integer n, where n ≥ 2.
Your program should support input up to the language's maximum integer value.


Output


Simply output the number of steps, like 6.
Leading/trailing whitespaces or newlines are fine.


Examples

f(5)        --&gt; 3
f(30)       --&gt; 6
f(31)       --&gt; 7
f(32)       --&gt; 5
f(100)      --&gt; 8
f(200)      --&gt; 9
f(2016^155) --&gt; 2015


Requirements


You can get input from STDIN, command line arguments, as function parameters or from the closest equivalent.
You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
This is code-golf so shortest answer in bytes wins.
Standard loopholes are disallowed.




This series can be found on OEIS as well: A064097


  A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n &gt; 1.
Jelly, 9 bytes
ÆṪÐĿÆFL€S

Try it online! or verify all test cases.
Background
The definition of sequence A064097 implies that

By Euler's product formula

where φ denotes Euler's totient function and p varies only over prime numbers.
Combining both, we deduce the property

where ω denotes the number of distinct prime factors of n.
Applying the resulting formula k + 1 times, where k is large enough so that φk+1(n) = 1, we get

From this property, we obtain the formula

where the last equality holds because ω(1) = 0.
How it works
ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.