#include<bits/stdc++.h>
using namespace std;
const int N = 2022;
vector<pair<int, int> > no[N];
int vis[N];
int dis[N];
int n = N - 1;
int gcd(int a, int b)
{
    return b?gcd(b, a%b):a;
}
void spfa(int ss)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[ss] = 0;
    priority_queue<pair<int, int> > q;
    q.push({-dis[ss], ss});
    while(!q.empty())
    {
        auto s = q.top().second;
        q.pop();
        vis[s] = 0;
        for(int i = 0; i < no[s].size(); ++i)
        {
            int t = no[s][i].first;
            int w = no[s][i].second;
            if(dis[t] > dis[s] + w)
            {
                dis[t] = dis[s] + w;
                q.push({-dis[t], t});
            }
        }
    }
}
int main()
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = max(1, i - 21); j <= min(n, i + 21); ++j)
        {
            int c = gcd(i, j);
            no[i].push_back({j, i*j/c});
            no[j].push_back({i, i*j/c});
        }
    }
    spfa(1);
    cout<<dis[n];
    return 0;
}