// Problem: I - Escape
// Contest: Virtual Judge - 思维
// URL: https://vjudge.net/contest/670080#problem/I
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=5e5+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/	



int f[N];
struct Node{
	int r=0;
	int s;
};
queue <Node> q;

signed main(){
	int k=rd;
	
	for(int i=0;i<N;i++)f[i]=INF;
	
	Node cur,cur2;
	for(int i=1;i<=9;i++){
		cur.r=i%k;
		cur.s=i*i;
		q.push(cur);
	}
	while(!q.empty()){
		cur2=q.front();
		q.pop();
		if(f[cur2.r]<=cur2.s)
			continue;
		f[cur2.r]=cur2.s;
		for(int i=0;i<=9;i++){
			cur.r=(10*cur2.r+i*i)%k;
			cur.s=cur2.s+i*i;
			q.push(cur);
		}
	}
	cout<<f[0];
}