#include<bits/stdc++.h>

const int INF = 100000000;

using namespace std;

int main(){
  int K;
  cin >> K;
  
  vector<int> rem(K, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  rem[1] = 1;
  pq.push({1, 1});
  
  while(pq.size()){
    auto [digits, node] = pq.top();
    pq.pop();
    
    if(rem[node] < digits) continue;
    
    if(digits + 1 < rem[(node + 1) % K]){
      rem[(node + 1) % K] = digits + 1;
      pq.push({digits + 1, (node + 1) % K});
    }
    
    if(digits < rem[node * 10 % K]){
      rem[node * 10 % K] = digits;
      pq.push({digits, node * 10 % K});
    }
  }
  
  cout << rem[0] << endl;
  
  return 0;
}