G - Decreasing Number

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5;
int n;
int dp[N];


signed main()
{
    dp[1] = 0;
    for(int i = 2; i <= 1e6; i++){
        dp[i] = dp[i - 1] + 1;
        if(i % 2 == 0)
            dp[i] = min(dp[i] , dp[i / 2] + 1);
        if(i % 3 == 0)
            dp[i] = min(dp[i] , dp[i / 3] + 1);
    }
    while(cin >> n){
        cout << dp[n] << endl;
    }
}