#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define pi pair<ll, ll>
#define pl pair<ll, pi>
#define fi first
#define se second
#define N 222222
ll n, ans, p, pw[N] = {1}, sum[N], dp[N], vis[N];
ll calc(ll n)
{
    ll ans = 0, t;
    while (n > 0)
    {
        t = n % 10;
        ans += (t * t);
        n /= 10;
    }
    return ans;
}
ll phi(ll x){
	ll ans = x;
	for(int i = 2 ; i <= x / i ; i++){
		if(x % i == 0){
			ans = x / i * (i - 1);
			while(x % i == 0)
				x /= i;
		}
	}
	return ans;
}
priority_queue<pl> q;
signed main()
{
    cin >> n;
    p = phi(n);
    for(int i = 1 ; i <= p ; i++)
    	pw[0] = pw[0] * 10 % n;
    sum[0] = pw[0];
    for(int i = 1 ; i < 2 * p ; i++){
    	pw[i] = pw[i - 1] * 10 % n;
    	sum[i] = (sum[i - 1] + pw[i]) % n;
	}
    dp[0] = calc(n);
    for(int i = 1 ; i <= 9 ; i++)
    	for(int j = 0 ; j < 2 * p ; j++){
    		if(dp[i * pw[j] % n])
    			continue;
			dp[i * pw[j] % n] = i * i;
			q.push({-i * i, {i * pw[j] % n, j}});
		}
	while(q.size()){
		pi u = q.top().se;
		q.pop();
		if(vis[u.fi])
			continue;
		if(!u.fi)
			break;
		if(dp[u.fi] >= dp[0])
			break;
		vis[u.fi] = true;
		for(ll t = 1 ; t <= 9 ; t++)
			for(ll r = u.se + 1 ; r < 2 * p ; r++){
				ll v = (u.fi + pw[r] * t % n) % n;
				if((dp[v] > dp[u.fi] + t * t) || (!dp[v]))
					q.push({-(dp[v] = (dp[u.fi] + t * t)), {v, r}});
			}
	}
	cout << dp[0];
    exit(0);
}