public static void solve ( ) {
  Scanner sc = new Scanner ( System . in ) ;
  int k = sc . nextInt ( ) ;
  Deque < Point > dq = new ArrayDeque < Point > ( ) ;
  boolean [ ] judge = new boolean [ k ] ;
  Arrays . fill ( judge , true ) ;
  Point now = new Point ( 1 , 1 ) ;
  dq . add ( now ) ;
  while ( ! dq . isEmpty ( ) ) {
    Point z = dq . removeFirst ( ) ;
    if ( ! judge [ ( z . x ) ] ) {
      continue ;
    }
    judge [ ( z . x ) ] = false ;
    if ( z . x == 0 ) {
      System . out . println ( z . y ) ;
      break ;
    }
    if ( judge [ ( z . x * 10 ) % k ] ) {
      dq . addFirst ( new Point ( ( z . x * 10 ) % k , z . y ) ) ;
    }
    if ( judge [ ( z . x + 1 ) % k ] ) {
      dq . addLast ( new Point ( ( z . x + 1 ) % k , z . y + 1 ) ) ;
    }
  }
}

public static void solve ( ) { Scanner sc = new Scanner ( System . in ) ; int k = sc . nextInt ( ) ; Deque < Point > dq = new ArrayDeque < Point > ( ) ; boolean [ ] judge = new boolean [ k ] ; Arrays . fill ( judge , true ) ; Point now = new Point ( 1 , 1 ) ; dq . add ( now ) ; while ( ! dq . isEmpty ( ) ) { Point z = dq . removeFirst ( ) ; if ( ! judge [ ( z . x ) ] ) { continue ; } judge [ ( z . x ) ] = false ; if ( z . x == 0 ) { System . out . println ( z . y ) ; break ; } if ( judge [ ( z . x * 10 ) % k ] ) { dq . addFirst ( new Point ( ( z . x * 10 ) % k , z . y ) ) ; } if ( judge [ ( z . x + 1 ) % k ] ) { dq . addLast ( new Point ( ( z . x + 1 ) % k , z . y + 1 ) ) ; } } }
(method_declaration (modifiers) type: (void_type) name: (identifier) parameters: (formal_parameters) body: (block (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (object_creation_expression type: (type_identifier) arguments: (argument_list (field_access object: (identifier) field: (identifier)))))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (method_invocation object: (identifier) name: (identifier) arguments: (argument_list)))) (local_variable_declaration type: (generic_type (type_identifier) (type_arguments (type_identifier))) declarator: (variable_declarator name: (identifier) value: (object_creation_expression type: (generic_type (type_identifier) (type_arguments (type_identifier))) arguments: (argument_list)))) (local_variable_declaration type: (array_type element: (boolean_type) dimensions: (dimensions)) declarator: (variable_declarator name: (identifier) value: (array_creation_expression type: (boolean_type) dimensions: (dimensions_expr (identifier))))) (expression_statement (method_invocation object: (identifier) name: (identifier) arguments: (argument_list (identifier) (true)))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (object_creation_expression type: (type_identifier) arguments: (argument_list (decimal_integer_literal) (decimal_integer_literal))))) (expression_statement (method_invocation object: (identifier) name: (identifier) arguments: (argument_list (identifier)))) (while_statement condition: (parenthesized_expression (unary_expression operand: (method_invocation object: (identifier) name: (identifier) arguments: (argument_list)))) body: (block (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (method_invocation object: (identifier) name: (identifier) arguments: (argument_list)))) (if_statement condition: (parenthesized_expression (unary_expression operand: (array_access array: (identifier) index: (parenthesized_expression (field_access object: (identifier) field: (identifier)))))) consequence: (block (continue_statement))) (expression_statement (assignment_expression left: (array_access array: (identifier) index: (parenthesized_expression (field_access object: (identifier) field: (identifier)))) right: (false))) (if_statement condition: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal))) consequence: (block (expression_statement (method_invocation object: (field_access object: (identifier) field: (identifier)) name: (identifier) arguments: (argument_list (field_access object: (identifier) field: (identifier))))) (break_statement))) (if_statement condition: (parenthesized_expression (array_access array: (identifier) index: (binary_expression left: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal))) right: (identifier)))) consequence: (block (expression_statement (method_invocation object: (identifier) name: (identifier) arguments: (argument_list (object_creation_expression type: (type_identifier) arguments: (argument_list (binary_expression left: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal))) right: (identifier)) (field_access object: (identifier) field: (identifier))))))))) (if_statement condition: (parenthesized_expression (array_access array: (identifier) index: (binary_expression left: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal))) right: (identifier)))) consequence: (block (expression_statement (method_invocation object: (identifier) name: (identifier) arguments: (argument_list (object_creation_expression type: (type_identifier) arguments: (argument_list (binary_expression left: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal))) right: (identifier)) (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (decimal_integer_literal)))))))))))))