def downToZero(n):
    if n <= 3:
        return n
    visited = set()
    queue = deque([(n, 0)])
    while queue:
        number, depth = queue.popleft()
        if number == 0:
            return depth
        if number not in visited:
            visited.add(number)
            queue.append((number-1, depth+1))
            i = 2
            while i * i <= number:
                if number % i == 0:
                    queue.append((max(i, number // i), depth + 1))
                i += 1

int downToZero(int n) {
    if (n==0) return 0;
    vector<bool> visited;
    visited.resize(n);
    
    vector<int> predecessor;
    predecessor.resize(n);
    
    // BFS
    queue<int> que;
    que.push(n);
    visited[n] = true;
    while (!que.empty()) {
        int t = que.front(); que.pop();
        
        int case1 = t - 1;
        if (!visited[case1]) {
            //cout << "-1-" << case1 << endl;
            visited[case1] = true;
            predecessor[case1] = t;
            que.push(case1);
        }
        for(int i = sqrt(t); i >= 2; i--) {
            if (t % i == 0 && !visited[t/i]) {
                //cout << "---" << t/i << endl;
                visited[t/i] = true;
                predecessor[t/i] = t;    
                que.push(t/i);

            }
        } 
        if (visited[0]) {
            break;
        } 
    }
    
    vector<int> rs;
    rs.push_back(0);
    int q = predecessor[0];
    while (q != n) {
        cout << q << endl;
        rs.push_back(q);
        q = predecessor[q];    
    }
    return rs.size();
}

class Result {

    public static ArrayList<Integer> getFactors(int n){
        ArrayList<Integer> factor=new ArrayList<>();
        
        for(int i=2;i<=Math.sqrt(n);++i){
            if(n%i==0){
                factor.add(Math.max(i,n/i));
            }
        }
        factor.add(n-1);
        return factor;
    }

    public static int downToZero(int n) {
        if(n==0){
            return 0;
        }
       int []vis=new int[n+1];
       
       Arrays.fill(vis,-1);
       
       Queue<Integer> q=new LinkedList<>();
       q.add(n);
       vis[n]=0;
       
       while(!q.isEmpty()){
           
           int front=q.remove();
           
           ArrayList<Integer> fact=getFactors(front);
           
           for(int num:fact){
               if(num==0){
                   return vis[front]+1;
               }
               if(vis[num]==-1){
                   vis[num]=vis[front]+1;
                   q.add(num);
               }
           }
       }
       
       return 0;

    }

}
****

import collections
def downToZero(n):
    # Write your code here
    ops = 0
    vals = [n]
    while True:
        newVals = []
        for val in vals:
            if val <= 3:
                return ops + val
            divisors = maxDivisors(val)
            if divisors != []:
                for div in divisors:
                    newVals.append(div)
            newVals.append(val - 1)
        ops += 1
        vals = sorted(list(set(newVals)))
        
def maxDivisors(n):
    div = int(math.sqrt(n))
    divisors = []
    while div >= 2:
        if n % div == 0:
            divisors.append(int(n/div))
        div -= 1
    
    return divisors