#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;
const int INF32 = 1e9;

int N, f[MAX_N];
priority_queue<pair<int,int>> pq;

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i ++) {
        f[i] = INF32;
    }
    for (int i = 1; i <= 9; i ++) {
        int j = i % N;
        if (f[j] > i * i) {
            f[j] = i * i;
            pq.push(make_pair(-f[j], j));
        }
    }
    while (pq.size()) {
        auto tmp = pq.top();
        pq.pop();
        int x = tmp.second;
        if (tmp.first != -f[x]) continue;
        for (int i = 0; i <= 9; i ++) {
            int y = (x * 10 + i) % N;
            if (f[y] > f[x] + i * i) {
                f[y] = f[x] + i * i;
                pq.push(make_pair(-f[y], y));
            }
        }
    }
    printf("%d\n", f[0]);
    return 0;
}