#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 1e5 + 100;
namespace dijkstra{
    vector<pair<int, ll>> g[N];
    bool vis[N];
    ll dis[N];
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    ll Dij(int s, int t){
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        ll _unr = dis[0];
        dis[s] = 0;
        q.push(make_pair(dis[s], s));
        while(!q.empty()){
            int u = q.top().second;q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i = 0;i < (int)g[u].size();i++){
                int v = g[u][i].first, w = g[u][i].second;
                if(dis[u] + w < dis[v]){
                    dis[v] = dis[u] + w;
                    q.push(make_pair(dis[v], v));
                }
            }
        }
        return dis[t];
    }
}
using namespace dijkstra;
int n;
int main(){
    cin >> n;
    for(int x = 1;x < n;x++){
        for(int r = 0;r <= 9;r++){
            int u = x, v = (x * 10 + r) % n, w = r * r;
            g[u].push_back({v, w});
        }
    }
    ll ans = 1e18;
    for(int s = 1;s < min(10, n);s++) ans = min(ans, Dij(s, 0) + s);   
    cout << ans << endl;
    return 0;
}