#include <cstdio>
#include <algorithm>
using namespace std;
int n, ans;
int pw10[610];
int dp[2][100010];
int main() {
    scanf("%d", &n);
    for (int i = 0; i <= 500; i++) {
        if (i == 0) pw10[i] = 1;
        else pw10[i] = pw10[i - 1] * 10 % n;
    }
    int flag = 0;
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1e9;
    }
    for (int i = 0; i <= 500; i++) {
        flag ^= 1;
        for (int j = 0; j < n; j++) {
            dp[flag][j] = 1e9;
        }
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < n; k++) {
                dp[flag][k] = min(dp[flag][k], dp[flag ^ 1][(k - j * pw10[i] % n + n) % n] + j * j);
            }
            if (j != 0) {
                dp[flag][j * pw10[i] % n] = min(dp[flag][j * pw10[i] % n], j * j);
            }
        }
    }
    printf("%d\n", dp[flag][0]);
    return 0;
}