1
#include <bits/stdc++.h>
2
#define ll long long
3
 
4
using namespace std;
5
 
6
int main() {
7
    std::ios_base::sync_with_stdio(false);
8
    cin.tie(0);
9
    cout.tie(0);
10
    int n;
11
    cin >> n;
12
    int dp[n + 1] = {};
13
    dp[1] = 0;
14
    for (int i = 2; i <= n; ++i) {
15
        dp[i] = dp[i - 1] + 1;
16
        if (i % 2 == 0) {
17
            dp[i] = min(dp[i], dp[i / 2] + 1);
18
        }
19
        if (i % 3 == 0) {
20
            dp[i] = min(dp[i], dp[i / 3] + 1);
21
        }
22
    }
23
    
24
    cout << dp[n];
25
    return 0;
26
}
27
 
28
 
29
 
30