public static int DownToZero(int n) {
    return new DownToZeroSolution().Solve(n);
}
    
class DownToZeroSolution {
    static int calculated_N;
    static readonly int[] solutions;

    static DownToZeroSolution() {
        calculated_N = 1;
        solutions = new int[1_000_001];
        solutions[1] = 1;
    }
    public int Solve(int n) {
        if(n <= calculated_N) return solutions[n];

        for(int i = calculated_N + 1; i <= n; i++) {
            solutions[i] = CalculateItem(i);
        }
        calculated_N = n;
        return solutions[n];
    }
    static int CalculateItem(int n) {
        int min = solutions[n - 1];
        int d_start;
        int d_step;

        if((n & 1) == 1) {
            d_start = 3;
            d_step = 2;
        }
        else {
            d_start = 2;
            d_step = 1;
        }
        
        int topN = (int)(Math.Sqrt(n) + 0.1);

        // n = d1*d2
        for(int d1 = d_start; d1 <= topN; d1 += d_step) {
            if(n % d1 == 0)
                min = Math.Min(min, solutions[Math.Max(d1, n / d1)]);
        }
        return 1 + min;
    }
}